Linear combinations euclidean algoritm extended

[sg001]

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

Homework Equations

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?

 

[HallsofIvy]

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.

 

[sg001]

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 there's only some ways it will work

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