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

Quote:

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)}$

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 $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}$.
• Aug 8th 2009, 08:28 AM
Soroban
Hello, geo2!

Quote:

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}$