• Support PF! Buy your school textbooks, materials and every day products Here!

Linear combinations euclidean algoritm extended!

  • Thread starter sg001
  • Start date
  • #1
134
0

Homework Statement



I have questions along the line of

Use the Euclidean Algorithm to find d= gcd(a,b) and x, y [itex]\in[/itex] [itex]Z[/itex] 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?
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
955
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.
 
  • #3
134
0
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?
 

Related Threads on Linear combinations euclidean algoritm extended!

  • Last Post
Replies
6
Views
335
Replies
0
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
3
Views
848
  • Last Post
Replies
3
Views
2K
Top