Euclidean algorithm

**geo2** · August 8th 2009, 12:20 AM

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?

**Failure** · August 8th 2009, 04:18 AM

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?

**geo2** · August 8th 2009, 05:49 AM

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

**Failure** · August 8th 2009, 07:54 AM

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

**Soroban** · August 8th 2009, 08:28 AM

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

Thread: Euclidean algorithm

LinkBack

Thread Tools

Display

Euclidean algorithm

Similar Math Help Forum Discussions

Euclidean Algorithm

Euclidean Algorithm

[SOLVED] Euclidean Algorithm

GCD and the Euclidean Algorithm

Euclidean Algorithm

Search Tags