# Thread: Finding GCD using Euclid's algorithm

1. ## Finding GCD using Euclid's algorithm

I am having trouble with this problem. I can work the problem to find the GCD but I cannot get it to work backwarks so that I can express it in
ma + nb form. Can anyone help me. The problem is for (116, -84)

2. Originally Posted by helpinmath
I am having trouble with this problem. I can work the problem to find the GCD but I cannot get it to work backwarks so that I can express it in
ma + nb form. Can anyone help me. The problem is for (116, -84)
Using the algorithm:

(116, -84) = (116, 84) = (32, 84) = (32, 20) = (12, 20) = (12, 8) = (4, 8) = (4, 4) = 4.

Working backwards:

4 = 8 - 4 = 8 - (12 - 8) = 2*8 - 12 = 2*(20 - 12) - 12 = 2*20 - 3*12 = 2*20 - 3*(32 - 20) = 5*20 - 3*32 = 5*(84 - 2*32) - 3*32 = 5*84 - 13*32 = 5*84 - 13*(116 - 84) = 18*84 - 13*116 = -18*(-84) - 13*116

3. I can see the substitution, but where did the 5*comes from?

4. Originally Posted by helpinmath
I can see the substitution, but where did the 5*comes from?
5*... shows up in several places. be specific as to what you are talking about

5. I guess I am just not getting it. I see the parenthesis is the substitution from the upper part. But throughout the problem there is multiplication and I do not know where those numbers are coming from. I am taking this class as a distant education with no help at all.

6. 2*(20 - 12) like here for instance, how did you get the two?

7. ## Euclid's algorithm

Here is another problem that I think I may have gotten,

(85,65)

5=3*85 + -4*65

Hope this is right!

8. Originally Posted by helpinmath
I guess I am just not getting it. I see the parenthesis is the substitution from the upper part. But throughout the problem there is multiplication and I do not know where those numbers are coming from. I am taking this class as a distant education with no help at all.
if finding the linear combination for the gcd is your objective as much as finding the gcd is, then i suggest using the matrix form of the Euclidean algorithm. have you ever heard of this? seen it?

anyway, as iceman said, you find the combination by working backwards.

now, obviously what you have is wrong, just work it out, 3*85 + (-4)65 = -5 not 5. it should be (-3)(85) + 4(65) perhaps. lets check

run the algorithm on (85,65)

85 = 1*65 + 20 ......................(1)
65 = 3*20 + 5 ........................(2)
20 = 4*5 + 0 ..........................(3)

so that 5 is the gcd(85,65)

Now to find the linear combination, start at line (2). (it will always be the case that you start at the second to last line)

we have 65 = 3*20 + 5

=> 5 = 65 - 3*20

now, we want to keep the 65, but we don't want the 20, we want a linear combination of 65 and 85, so change 20 based on line (1)

=> 5 = 65 - 3(85 - 1*65)
=> 5 = 65 - 3*85 + 3*65
=> 5 = 4*65 + (-3)*85

and there's our linear combination. you apply the same concept to longer algorithms. just repeatedly change out numbers you don't want based on the previous line they appear in.

now lets see how the matrix method works. you basically apply the same algorithm, but keep track of remainders in a matrix

So, we want to find $(85,65)$, so we set up a matrix in the following way. treat (85,65) as (x,y) and we will set up an augmented matrix based on the system:

1*85 + 0*65 = 85
0*85 + 1*65 = 65

so 85 is your x and 65 is your y. now if you were to solve this system using matrices (or, in a weird way, unsolve it, since this is already in reduced row-echelon form), you would do the following

$\left( \begin{array}{ccc} 1 & 0 & 85 \\ 0 & 1 & 65 \end{array} \right)$ $\begin{array}{l} \text{...R1} \\ \text{...R2} \end{array}$
------------------------------
$\left( \begin{array}{ccc} 0 & 1 & 65 \\ 1 & -1 & 20 \end{array} \right)$ $\begin{array}{l} \text{...R2} \\ \text{...R1 - R2} \end{array}$
------------------------------
$\left( \begin{array}{ccc} 1 & -1 & 20 \\ -3 & 4 & 5 \end{array} \right)$ $\begin{array}{l} \text{...R2} \\ \text{...R1 - 3*R2} \end{array}$
------------------------------
$\left( \begin{array}{ccc} -3 & 4 & 5 \\ 13 & -17 & 0 \end{array} \right)$ $\begin{array}{l} \text{...R2} \\ \text{...R1 - 4*R2 ...we get 0 here, so we stop the algorithm} \end{array}$

now, remember, the first column represents our x value, which is 85, and the second represents our y value, which is 65. so the first row of the last matrix says: -3*x + 4*y = -3*85 + 4*65 = 5

and there is our combination. so in one swoop, we find the linear combination and the gcd

9. Thanks for the breakdown of that problem. I have tried to use it to do another one but I get stuck half way down using the matrix. Here is what I have so far...

(116, -84)

1 0 116
0 1 84
0 1 84
1 -1 32
1 -1 32
-2 3 20 Here is where I get stuck. The number seems to get higher instead of lower.

10. ## Another Problem using matrix

(72, 26) Using matrix algorithm

I am still getting stuck down in the middle.

1 0 72
0 1 26
0 1 26
1 -1 46
1 -1 46 Here is where I get stuck.

And another:

(72,25)

1 0 72
0 1 25
0 1 25
1 -1 47
1 -1 47
-2 3 -69 I do not think this is right.

11. For the first problem, remember to keep subtracting x until you get a number less than x.

1; 0; 72
0; 1; 26

changes to

0; 1; 26
1; -2; 20

continuing...

1; -2; 20
-1; 3; 6
----------
-1; 3; 6
4; -11; 2
----------
4; -11; 2
-13; 36; 0

Hence 4*72 - 11*26 = 2

and the GCD is 2.

12. ## I hope this is right for (72, 25)

I hope this is right for (72, 25)

1 0 72
0 1 25
0 1 25
1 -2 22
1 -2 22
-1 3 3
-1 3 3
0 1 0

13. Originally Posted by Mel
I hope this is right for (72, 25)

1 0 72
0 1 25
0 1 25
1 -2 22
1 -2 22
-1 3 3
-1 3 3
0 1 0
actually it's not. and it's not that hard to see. the first thing that should scream it out to you is that you end up with a line that says 0 1 0. and we know this can't be right, since you began with 0 1 25. you can't have a number equaling zero and 25 at the same time. secondly, according to this, the gcd is 3. this is of course absurd, as 3 does not divide 25

14. Thanks for you wonderful words of wisdom. I am trying though to do this on my own, I am not just looking for answers. Sorry!

15. Originally Posted by helpinmath
Thanks for you wonderful words of wisdom. I am trying though to do this on my own, I am not just looking for answers. Sorry!
so you like the matrix method, huh?

your professor won't have a problem with you doing it this way, will he/she?

Page 1 of 2 12 Last