# Linear combinations euclidean algoritm extended!

## Homework Statement

I have questions along the line of

Use the Euclidean Algorithm to find d= gcd(a,b) and x, y $\in$ $Z$ with d= ax +by

## The Attempt at a Solution

Ok so I use the euclidean algorithm as I know it on say gcd (83,36), by minusing of the the lowest number and repeating until i get the last non zero remainder ie, the gcd but I am completely lost on how to find the form ax +by, I know there must be some technique other than guessing and trial and error....
anyone care to let me in?

Related Calculus and Beyond Homework Help News on Phys.org
HallsofIvy
Homework Helper
Yes, 36 divides into 83 twice with remainder 11: (I) 11= 83- 2(36).

Then 11 divides into 36 three times with remainder 3: (II) 3= 36- 3(11).

3 divides into 11 three times with remainder 2: (III) 2= 11- 3(3).

Finally, 2 divides into 3 once with remainder 1: (IV) 1= 3- 2 which tells us that the least common denominator is 1. (36 and 83 are "relatively prime".)

Now replace the "2" in equation (IV) with "11- 3(3)" from (III) to get
1= 3- (11- 3(3))= 3- 11+ 3(3)= 4(3)- 11.

Then replace the "(3)" in that equation by "36- 3(11)" from (II) to get
1= 4(36- 3(11))- 11= 4(36)- 12(11)- 11= 4(36)- 13(11).

Finally, replace the "(11)" in that equation by "83- 2(36)" from (I) to get
1= 4(36)- 11(83- 2(36))= 4(36)- 11(83)+ 22(36)= 26(36)- 11(83).

That is "d= ax+ by" with d=1, a= -11, b= 26.

Yes, 36 divides into 83 twice with remainder 11: (I) 11= 83- 2(36).

Then 11 divides into 36 three times with remainder 3: (II) 3= 36- 3(11).

3 divides into 11 three times with remainder 2: (III) 2= 11- 3(3).

Finally, 2 divides into 3 once with remainder 1: (IV) 1= 3- 2 which tells us that the least common denominator is 1. (36 and 83 are "relatively prime".)

Now replace the "2" in equation (IV) with "11- 3(3)" from (III) to get
1= 3- (11- 3(3))= 3- 11+ 3(3)= 4(3)- 11.

Then replace the "(3)" in that equation by "36- 3(11)" from (II) to get
1= 4(36- 3(11))- 11= 4(36)- 12(11)- 11= 4(36)- 13(11).

Finally, replace the "(11)" in that equation by "83- 2(36)" from (I) to get
1= 4(36)- 11(83- 2(36))= 4(36)- 11(83)+ 22(36)= 26(36)- 11(83).

That is "d= ax+ by" with d=1, a= -11, b= 26.
Thanks that makes sense although I was hoping I could have acheived the result by ie gcd(83,36) =

83-36 =47 -36 = 36 -11 = 25 -11 = 14-11 = 11-3 = 8-3 = 5-3 = 3-2 = 2-1 = 1 !

and then I was hoping the coefficients would lie in there somewhere...

but I guess theres only some ways it will work

by the way how did you get the 13 in the fifth paragraph on the last expression?