Results 1 to 5 of 5

Math Help - Extended euclidean algorighm question

  1. #1
    Junior Member
    Joined
    Aug 2008
    Posts
    44

    Extended euclidean algorighm question

    I have some confusions about the procedure of extended EQ

    say: gcd(81, 57)=3
    here is what I did:

    81=1*57+24
    57=2*24+9
    24=2*9+6
    9=1*6+3
    6=2*3+0

    then I have problems when I do it from way back

    3 = 9 -1(6)

    From the line before that, I get 6 = 24 - 2(9), so:

    3 = 9 - 1(24 - 2(9)) = ??

    then I have no idea what to do. my friend give me this = 3(9) - 1(24), and I dont know where this comes from.


    here is the solution he gave me, and I dont know where are all those underlined numbers come from, second part after the equal sign, how to substitute those numbers.

    From the line before that, we see that 6 = 24 - 2(9), so:
    3 = 9 - 1(24 - 2(9)) = 3(9) - 1(24).
    From the line before that, we have 9 = 57 - 2(24), so:
    3 = 3( 57 - 2(24)) - 1(24) = 3(57) - 7(24).
    And, from the line before that 24 = 81 - 1(57), giving us:
    3 = 3(57) - 7( 81 - 1(57)) = 10(57) -7(81).

    Anyone give me a detailed explain..Thank you. I am struggling.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Lol i could see either then I realized how ridiculously obvious it is... expand the brackets!

    3 = 9 - 1(24 - 2(9)) = 9 - 1(24) + 2(9) = 3(9) - 1(24).

    Others are the same.

    Second one would be,

    3 = 3( 57 - 2(24) ) - 1(24) = 3(57) - 3*2(24) - 1(24) = 3(57) - 6(24) - 1(24) = 3(57) - 7(24).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2008
    Posts
    44
    Quote Originally Posted by Deadstar View Post
    Lol i could see either then I realized how ridiculously obvious it is... expand the brackets!

    3 = 9 - 1(24 - 2(9)) = 9 - 1(24) + 2(9) = 3(9) - 1(24).
    Thanks, now I get it. It's just expand it and combine the "like terms".
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    yeah thats it.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2008
    Posts
    44
    Quote Originally Posted by Deadstar View Post
    yeah thats it.
    well, I did a couple of problems, and its getting better~
    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. GCD and extended euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: December 11th 2010, 05:25 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