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
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 $\displaystyle (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
$\displaystyle \left( \begin{array}{ccc} 1 & 0 & 85 \\ 0 & 1 & 65 \end{array} \right)$$\displaystyle \begin{array}{l} \text{...R1} \\ \text{...R2} \end{array}$
------------------------------
$\displaystyle \left( \begin{array}{ccc} 0 & 1 & 65 \\ 1 & -1 & 20 \end{array} \right)$$\displaystyle \begin{array}{l} \text{...R2} \\ \text{...R1 - R2} \end{array}$
------------------------------
$\displaystyle \left( \begin{array}{ccc} 1 & -1 & 20 \\ -3 & 4 & 5 \end{array} \right)$$\displaystyle \begin{array}{l} \text{...R2} \\ \text{...R1 - 3*R2} \end{array}$
------------------------------
$\displaystyle \left( \begin{array}{ccc} -3 & 4 & 5 \\ 13 & -17 & 0 \end{array} \right)$$\displaystyle \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
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.
(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.
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.
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