Results 1 to 8 of 8

Math Help - GCD and extended euclidean algorithm

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    7

    GCD and extended euclidean algorithm

    I have the following problem for homework:
    Compute gcd(57,93), and find integers s and t such that 57s + 93t = gcd(57,93).

    Now I have computed gcd(57,93) = 3 using the Extended Euclidean Algorithm. I am a bit lost on the second part of the question. I was wondering if somebody could help me start or lead me in the right direction as to how to solve the second part.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    \displaystyle 93=1*57+36\rightarrow 36=93-1*57

    \displaystyle 57=1*36+21\rightarrow 21=57-1*36

    \displaystyle 36=1*21+15\rightarrow 15=36-1*21

    \displaystyle 21=1*15+6\rightarrow 6=21-1*15

    \displaystyle 15=2*6+3\rightarrow 3=15-2*6

    \displaystyle 6=2*3+0

    Can you take it from here?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2010
    Posts
    7
    That is what I used to find the gcd. I don't really know what the second part is asking me to do, or how to do it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    \displaysyle 3=15-2*6=15-2*(21-1*15)=15-2*21+2*15=15*3-2*21=3*(36-1*21)-2*21=\cdots
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2010
    Posts
    7
    Not to sound ungrateful for you quick responses, but could you explain that a little. I don't really understand what you are doing there.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    I am taking the GCD of 3 in the last equation and isolating it on one side of the equation. I then do the same for all the remainders. Then in each equation you will see, for instance, 3 = 15 - 2*6 but above this we have 6 = 21-1*15. By substitution, we obtain 3 = 15 - 2*(21-1*15). Then we simplify and continue to substitute.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2010
    Posts
    7
    Okay, thank you very much for the clarification. I continued that and ended up with 3 = 8 X 93 - 13 X 57. Thus making s = -13 and t = 8.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,967
    Thanks
    1635
    The problem is to solve 57s + 93t = gcd(57,93)= 3. Divide both sides of the equation by 3 to get 19s+ 31t= 1

    (1) 19 divides into 31 once with remainder 12. 31- 19= 12

    (2) 12 divides into 19 once with remainder 7. 19- 12= 7

    (3) 7 divides into 12 once with remainder 5. 12- 7= 5

    (4) 5 divides into 7 once with remainder 2. 7- 5= 2

    (5) 2 divides into 5 twice with remainder 1: 5- 2(2)= 1

    Replace that '2" with 7- 5 from (4): 5- 2(7- 5)0= 3(5)- 2(7)= 1

    Replace that "5" with 12- 7 from (3): 3(12- 7)- 2(7)= 3(12)- 5(7)= 1

    Replace that "7" with 19- 12 from (2): 3(12)- 5(19- 12)= 8(12)- (5)19= 1

    Replace that "12" with 31- 19 from (1): 8(31- 19)- 5(19)= (8)31- (13)(19)= 1

    Comparing that with 19s+ 31t= 1 we can take s= -13 and t= 8.

    Notice, by the way that is s= -13+ 31k and t= 8- 19k then 19s+ 31t= 19(-13)+ (19)(31)k+ 31(8)- 19(31)k= 1 since the "19(31)k" terms cancel.

    Any pair of integers s= -13+ 31k and t= 9- 19k for any integer k, satisfy the equation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Extended Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 17th 2011, 07:27 AM
  2. Extended euclidean algorighm question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 4th 2009, 10:16 AM
  3. Extended Euclidean algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 21st 2009, 01:24 PM
  4. Replies: 6
    Last Post: March 31st 2009, 05:44 PM
  5. Extended Euclidean related polynomial's inverse
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: October 12th 2008, 12:59 PM

Search Tags


/mathhelpforum @mathhelpforum