# Euclidean algorithm

• Aug 8th 2009, 12:20 AM
geo2
Euclidean algorithm
Please someone help me with this I am confused(Crying)

1) find the Highest common Factor of 54735 and 238965
2) find the Lowest Common Multiple of 54735 and 238965
3) find the solution to the linear congruence 54735a + 238965b = 16020

and finally explain why there are an infinite number of solution to this linear congruence and find one more solution?
• Aug 8th 2009, 04:18 AM
Failure
Quote:

Originally Posted by geo2
Please someone help me with this I am confused(Crying)

1) find the Highest common Factor of 54735 and 238965

To determine $\displaystyle \mathrm{gcd}(a,b)$ you repeatedly replace the larger of the two numbers by the remainder of the larger divided by the smaller .. until the lager is a multiple of the smaller. In your case I get

$\displaystyle \begin{array}{lcl} \mathrm{gcd}(238965,54735) &=& \mathrm{gcd}(54735,20025)\\ &=& \mathrm{gcd}(20025,14685)\\ &=& \mathrm{gcd}(14685,5340)\\ &=& \mathrm{gcd}(5340,4005)\\ &=& \mathrm{gcd}(4005,1335)\\ &=& 1335 \end{array}$
The last equality sign holds, because 4005 is a multiple of 1335.

Quote:

2) find the Lowest Common Multiple of 54735 and 238965
Just remember that $\displaystyle \mathrm{lcm}(a,b)=\frac{a\cdot b}{\mathrm{gcd}(a,b)}$

Quote:

3) find the solution to the linear congruence 54735a + 238965b = 16020

and finally explain why there are an infinite number of solution to this linear congruence and find one more solution?
• Aug 8th 2009, 05:49 AM
geo2
thanks for the help!!for the third one you know what i have to do??
• Aug 8th 2009, 07:54 AM
Failure
Quote:

Originally Posted by geo2
Please someone help me with this I am confused(Crying)

3) find the solution to the linear congruence 54735a + 238965b = 16020

and finally explain why there are an infinite number of solution to this linear congruence and find one more solution?

So let's consider an equation of the form $\displaystyle u a+v b=c$ with $\displaystyle u,v, a,b,c\in \mathbb{Z}$.
First, $\displaystyle c$ must be a multiple of $\displaystyle \mathrm{gcd}(u,v)$ for integer solutions $\displaystyle a,b\in\mathbb{Z}$ to exist: because the left side of the equation is obviously an integer multiple of $\displaystyle \mathrm{gcd}(u,v)$, if $\displaystyle a,b\in\mathbb{Z}$
In your case, with $\displaystyle u=54735, v = 238965, c = 16020, \mathrm{gcd}(u,v)=1335$ this condition is satisfied.

Now you separate the problem of finding the general solution into two parts:
1. finding the general solution of the associated homogeneous equation $\displaystyle u a+vb=0$ and

2. finding a single, aka. "particular" solution of the original equation $\displaystyle ua+vb=c$.
Since the difference of two solutions of the original equation is a solution of the associated homogeneous equation, you then have found the general solution of the original equation: which is the sum of your particular solution of the original equation and the general solution of the homogeneous equation.

Ad 1.: Finding the general solution of the homogeneous equation $\displaystyle ua+vb=0$. Obviously $\displaystyle ua$ and $\displaystyle vb$ must be simultaneously integers and multiples of each other. Therefore the "smallest" integer solution has the form $\displaystyle a := \tfrac{v}{\mathrm{gcd}(u,v)}, b := -\tfrac{u}{\mathrm{gcd}(u,v)}$. The general solution of the homogeneous equation is an arbitrary integral multiple of this.

Ad 2.: You need to execute the extended version of the Euclidian Algorithm to find a solution $\displaystyle (x,y)$ of the equation $\displaystyle ux+vy=\mathrm{gcd}(u,v)$. Then you multiply that pair $\displaystyle (x,y)$ of integers with $\displaystyle \tfrac{c}{\mathrm{gcd}(u,v)}$ to get the desired particular solution of the orignal equation. Let's call it $\displaystyle (a_p,b_p)$.

Finally to write down the general solution of the original equation, which is $\displaystyle a := a_p+\tfrac{v}{\mathrm{gcd}(u,v)}\cdot n, b := b_p-\tfrac{u}{\mathrm{gcd}(u,v)}\cdot n, n\in \mathbb{Z}$.
• Aug 8th 2009, 08:28 AM
Soroban
Hello, geo2!

Quote:

3) Find the solution to the linear congruence: .$\displaystyle 54,\!735a + 238,\!965b \:=\: 16,\!020$

Explain why there are an infinite number of solutions to this linear congruence
and find one more solution.

We have: .$\displaystyle 54,\!735a + 238,\!965b \;=\;16,\!020$

Divide by 1335: .$\displaystyle 41a + 179b \;=\;12$

Solve for $\displaystyle a\!:\quad{\color{blue}[1]}\;a \:=\:\frac{12-179b}{41} \;=\;-4b + \frac{12-15b}{41} \quad\Rightarrow\quad a \;=\;-4b + \frac{3(4-5b)}{41}$

Since $\displaystyle a$ is an integer, $\displaystyle 4-5b$ must be a multiple of 41.

. . That is: .$\displaystyle 4-5b \:=\:41c \quad\Rightarrow\quad{\color{blue}[2]}\;b \:=\:\frac{4-41c}{5} \quad\Rightarrow\quad b \;=\;-8c + \frac{4-c}{5}$

Since $\displaystyle b$ is an integer, $\displaystyle 4-c$ must be a multiple of 5.

This happens if: .$\displaystyle c \;=\;-1+5m\;\text{ for some integer }m$

Substitute into [2]: .$\displaystyle b \;=\;\frac{4-41(-1+5m)}{5} \quad\Rightarrow\quad\boxed{ b \:=\:9-41m }$

Substitute into [1]: .$\displaystyle a \;=\;\frac{12 - 179(9-41m)}{41} \quad\Rightarrow\quad\boxed{ a \;=\;\text{-}39 + 179m}$

The solutions are: . $\displaystyle \boxed{\begin{array}{ccc}a&=& \text{-}39 + 179m \\ b &=& 9-41m \end{array}\;\text{ for {\color{red}any} integer }m}$

And that's why there is an infinite number of solutions.

. . $\displaystyle \begin{array}{|c|c|} \hline m & (a,b) \\ \hline \hline 0 & (\text{-}39,9) \\ 1 & (140,\text{-}32) \\ \vdots & \vdots \end{array}$