Results 1 to 2 of 2

Math Help - I can't seem to make Euclidean work backwards either. :/

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    1

    I can't seem to make Euclidean work backwards either. :/

    Use the extended Euclidean algorithm to find 198^-1 mod 257.

    Here's what I have:

    257 = 198 x 1 + 59
    198 = 59 x 3 + 21
    59 = 21 x 2 + 17
    21 = 17 x 1 + 4
    17 = 4 x 4 + 1

    Backwards:
    1 = 17 - 4 x 4
    1 = 17 - 4 (21 - 17)
    1 = 5 x 17 - 4 x 21
    1 = 5 x (59 - 21 x 2) - 4 x 21
    I worked a little more and think I got this:
    1 = 5 x 59 - 14 x 21 (this was by trial and error of some sort)
    1 = 5 x 59 - 14 x (198 - 59 x 3)
    And I'm stuck again.

    And that's where I'm stuck. I'm pretty sure it's having multiplication in the () that's screwing me up, not sure I worked with it before.. and if I have, I just don't get it.
    Last edited by aeval; September 30th 2008 at 09:23 AM. Reason: Figured some more out? Maybe?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Here's what I have:

    257 = 198 x 1 + 59 (1)
    198 = 59 x 3 + 21 (2)
    59 = 21 x 2 + 17 (3)
    21 = 17 x 1 + 4 (4)
    17 = 4 x 4 + 1 (5)

    Backwards:
    1 = 17 - 4 x 4
    1 = 17 - 4 (21 - 17)
    1 = 5 x 17 - 4 x 21
    1 = 5 x (59 - 21 x 2) - 4 x 21
    I worked a little more and think I got this:
    1 = 5 x 59 - 14 x 21 (this was by trial and error of some sort)
    Yes.

    1=5x(59-21x2)-4x21
    1=5x59-10x21-4x21
    1=5x59-14x21

    Then from (2), we have 21=198-59x3
    This makes :
    1=5x59-14x(198-59x3)
    1=5x59-14x198+59x52
    1=57x59-14x198

    Last step : from (1), we have 59=257-198

    1=57x(257-198)-14x198
    1=57x257-57x198-14x198
    1=57x257-71x198

    So -71x198=1-57x257
    -71x198=1 mod 257

    find what -71 mod 257 is and you have your answer.


    for the () stuff, you just have to keep an eye over the successive remainders. (they're in color above)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Can't make simple iteration work
    Posted in the Calculus Forum
    Replies: 5
    Last Post: August 4th 2010, 04:03 AM
  2. How to make generic filenames work in matlab?
    Posted in the Math Software Forum
    Replies: 1
    Last Post: June 9th 2010, 08:25 PM
  3. Correct but backwards?
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 2nd 2009, 01:19 PM
  4. Replies: 3
    Last Post: December 1st 2008, 12:53 PM
  5. Replies: 3
    Last Post: September 29th 2008, 12:31 PM

Search Tags


/mathhelpforum @mathhelpforum