Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By Deveno

Math Help - Euclids Algorithm and Multiple Inverses

  1. #1
    Member
    Joined
    May 2009
    Posts
    109

    Euclids Algorithm and Multiple Inverses

    r_{m-2} = q_{m} r_{m-1} + r_{m} \hspace{50}       0 < r_{m} < r_{m-1} \\* r_{m-1} = q_{m+1} r_{m} + 0

    (ignore the indentation on the first line)

    "The final equation shows that r_{m} is a factor of r_{m-1}, and then the penultimate equation shows that  r_{m} is also a factor of r_{m-2}. Continuing in this way, we find that r_{m} is a factor of all the remainders,"

    But isn't this obviously not true?

    r_{m-3} = q_{m-1}r_{m-2} + r_{m-1}

    So in the very next line r_{m} is no longer a factor.

    What am I not seeing?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: Euclids Algorithm and Multiple Inverses

    rm-3 = qm-1rm-2 + rm-1.

    but rm-2 = qmrm-1 + rm.

    so rm-3 = qm-1(qmrm-1 + rm) + rm-1 = (qm-1qm + 1)rm-1 + qm-1rm

    finally, since rm-1 = qm+1rm, we have:

    rm-3 = (qm-1qm + 1)(qm+1rm) + qm-1rm

    = (qm-1qmqm+1 + qm + qm-1)rm,

    so it certainly appears that rm does indeed divide rm-3.

    let's look at a specific example:

    suppose we wish to find gcd(33,138).

    first we divide 138 by 33 and compute the remainder:

    138 = 4*33 + 6

    next, we repeat the process by dividing 33 by 6:

    33 = 5*6 + 3

    and again, we divide 6 by 3:

    6 = 2*3 + 0 <--we got to 0, so our "final remainder" is the one in the second step: 3. without doing the "long division" we can show that 3 divides 138:

    138 = 4*33 + 6 = 4*(5*6 + 3) + 6 = (4*5 + 1)(6) + 4*3 = (4*5 + 1)(2)(3) + 4*3 = [(4*5 + 1)(2) + 4](3) = [(21)(2) + 4](3) = (42 + 4)(3) = (46)(3).

    note that we showed in the 2nd step that 3 divides 33 as well, since the 3rd step shows that 3 divides 6.

    perhaps a longer, less trivial example will show this more clearly:

    compute gcd(527,2261).

    2261 = (4)(527) + 153

    527 = (3)(153) + 68

    153 = (2)(68) + 17

    68 = (4)(17)

    working backwards, we have:

    153 = (2)(68) + 17 = (2)(4)(17) + 17 = ((2)(4) + 1)(17)

    527 = (3)(153) + 68 = (3)[(2)(68) + 17] + (4)(17) = (3)(2)(4)(17) + (3)17 + (4)(17) = [(2)(3)(4) + 4 + 3](17) <--17 divides 527

    2261 = (4)(527) + 153 = (4)[(2)(3)(4) + 4 + 3](17) + ((2)(4) + 1)(17) = [(4)(2)(3)(4) + (4)4 + (4)3 + (2)(4) + 1](17) <--17 divides 2261

    = (96 + 16 + 12 + 8 + 1)(17) = (133)(17)

    the remainders in this case were:

    68 (= (4)(17))
    153 ( = (2)(68) + 17 = (2)(4)(17) + 17 = ((2)(4) + 1)(17) = (9)(17))
    527 ( = [(2)(3)(4) + 4 + 3](17) = (31)(17))

    so in point of fact, 17 indeed divides every single one.
    Thanks from alyosha2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    109

    Re: Euclids Algorithm and Multiple Inverses

    Excellent, thanks. Great explanation, makes total sense now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 8th 2010, 07:55 AM
  2. [SOLVED] Euclids algorithm & congruence equations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 17th 2010, 10:10 PM
  3. Inverses
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 2nd 2010, 04:34 AM
  4. Least common multiple of multiple numbers
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 7th 2009, 09:18 PM
  5. Modification of proof of Euclids Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 10th 2007, 06:06 PM

Search Tags


/mathhelpforum @mathhelpforum