Results 1 to 2 of 2

Math Help - Extended Euclidean Algorithm

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1

    Extended Euclidean Algorithm

    Hi all, ok so below is an example of the Extended Euclidean Algorithm, and i understand the first part perfectly to find the g.c.d.

    701 − 2 322 = 57,
    322 − 5 57 = 37,
    57 − 37 = 20,
    37 − 20 = 17,
    20 − 17 = 3,
    17 − 5 3 = 2,
    3 − 2 = 1,

    and

    1 = 3 − 2
    = 6 3 − 17
    = 6 20 − 7 17
    = 13 20 − 7 37
    = 13 57 − 20 37
    = 113 57 − 20 322
    = 113 701 − 246 322.

    Now on the second part, it is finding the equation of ax +by = 1, which i am generally having to find so i can compute the inverse of a(modb). They have managed to do this in 7 steps. It always takes me like more than twice as many in a really longwinded fashion. Has the example below missed out some steps for the sake of conciseness? I just dont understand how they are doing what they are doing.

    For example I would have said

    1= 3- 2
    1 = (20-17) - (17 - (5x3))
    1 = ((57-37) - (37-20)) - ((37-20) - 5(20-17))
    etc.

    Which is obviously far more longwinded, but equally as methodical. I want to know how to do this more concisely so in an exam it would be far less confusing and time consuming.

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    May 2011
    Posts
    8
    Now on the second part, it is finding the equation of ax +by = 1, which i am generally having to find so i can compute the inverse of a(modb). They have managed to do this in 7 steps. It always takes me like more than twice as many in a really longwinded fashion. Has the example below missed out some steps for the sake of conciseness? I just dont understand how they are doing what they are doing.

    For example I would have said

    1= 3- 2
    1 = (20-17) - (17 - (5x3))
    1 = ((57-37) - (37-20)) - ((37-20) - 5(20-17))
    etc.

    Which is obviously far more longwinded, but equally as methodical. I want to know how to do this more concisely so in an exam it would be far less confusing and time consuming.

    For the most part, I think these problems are just plain tedious! Books just tend to leave out all of the "longwinded" dirty work just so that it looks nice in print.

    Your method looks like it works just fine, but as you continue on, it can get pretty messy. I just worked out this problem in 14 lines. When I do it, I simplify as much as I can before I move on to the next step, so that I don't lose track of where I am; and it saves from having to do all of the simplifying at the end. Heres how I do it:

    1 = 3 + (-1)2
    = 3 + (-1)[17 + (-3)5]
    = (-1)17 + 6(3) simplified
    = (-1)17 + 6[20 + (-1)17] next step
    = (6)20 + (-7)17 simplified
    = (6)20 + (-7)[37 + (-1)20] next step
    = (-7)37 + (13)20 .
    . .
    . .
    .
    = (-20)322 + (113)[701 + (-2)322]
    = (113)701 + (-246)322

    On exams, I would have a spot on the paper where I put the "concise 7-step" part and on the side or on scratch paper I would have all of the dirtywork of simplifying. That definitely makes things look neater for the grader.

    It just takes some practice to get used to the Euclidean Method.

    Oh, and if you think that this is such a messy longwinded method of doing this, just wait, you'll probably have to do the Euclidean Method with polynomials instead of integers one of these days!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. GCD and extended euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: December 11th 2010, 05:25 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