# Math Help - Euclidean algorithm

1. ## Euclidean algorithm

Please someone help me with this I am confused

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?

2. Originally Posted by geo2
Please someone help me with this I am confused

1) find the Highest common Factor of 54735 and 238965
To determine $\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

$\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.

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

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?

3. thanks for the help!!for the third one you know what i have to do??

4. Originally Posted by geo2
Please someone help me with this I am confused

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 $u a+v b=c$ with $u,v, a,b,c\in \mathbb{Z}$.
First, $c$ must be a multiple of $\mathrm{gcd}(u,v)$ for integer solutions $a,b\in\mathbb{Z}$ to exist: because the left side of the equation is obviously an integer multiple of $\mathrm{gcd}(u,v)$, if $a,b\in\mathbb{Z}$
In your case, with $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 $u a+vb=0$ and

2. finding a single, aka. "particular" solution of the original equation $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 $ua+vb=0$. Obviously $ua$ and $vb$ must be simultaneously integers and multiples of each other. Therefore the "smallest" integer solution has the form $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 $(x,y)$ of the equation $ux+vy=\mathrm{gcd}(u,v)$. Then you multiply that pair $(x,y)$ of integers with $\tfrac{c}{\mathrm{gcd}(u,v)}$ to get the desired particular solution of the orignal equation. Let's call it $(a_p,b_p)$.

Finally to write down the general solution of the original equation, which is $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}$.

5. Hello, geo2!

3) Find the solution to the linear congruence: . $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: . $54,\!735a + 238,\!965b \;=\;16,\!020$

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

Solve for $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 $a$ is an integer, $4-5b$ must be a multiple of 41.

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

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

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

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

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

The solutions are: . $\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.

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