1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear combinations euclidean algoritm extended!

  1. Mar 30, 2012 #1
    1. The problem statement, all variables and given/known data

    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



    2. Relevant equations



    3. 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?
     
  2. jcsd
  3. Mar 30, 2012 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  4. Mar 30, 2012 #3
    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Linear combinations euclidean algoritm extended!
  1. Linear combination (Replies: 16)

  2. Linear Combinations (Replies: 3)

  3. Linear combinations? (Replies: 1)

  4. Linear combination (Replies: 2)

Loading...