Results 1 to 3 of 3

Math Help - Another modular inverse question

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    21

    Another modular inverse question

    Alright, so I am working a modular inverse problem. The problem is "Use the Euclidean algorithm to find the inverse of of 47 modulo 151."

    So I start off with:

    151 = 3 * 47 + 10
    47 = 4 * 10 + 7
    10 = 1 * 7 + 3
    7 = 2 * 3 + 1
    3 = 3 * 1 + 0

    Then I rewrite so I can solve for s and t

    10 = 151 - 3 * 47
    7 = 47 - 4 * 10
    3 = 10 - 1 * 7
    1 = 7 - 2 * 3

    Then I setup to find s and t

    1 = 7 - 2 * 3
    1 = 7 - 2 ( 10 - 1 * 7 )
    1 = 7 - 2 * 10 + 2 * 7
    1 = -2 * 10 + 3 * 7
    1 = -2 * 10 + 3 ( 47 - 4 * 10 )
    1 = -2 * 10 + 3 * 47 + 12 * 10
    1 = 3 * 47 - 14 * 10
    1 = 3 * 47 - 14 (151 - 3 * 47 )
    1 = 3 * 47 - 14 * 151 + 42 * 47
    1 = -14 * 151 + 45 * 47

    s = -14
    t = 45

    So I found this website:
    Modular inversion - Fast mod inverse calculator

    And when I plug in 47 for n and 151 for p

    It tells me the modular inverse is 45.

    So is the modular inverse the same as t? And if not how do I solve for the modular inverse using the Euclidean Algorithm.

    cheers/thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by ipatch View Post
    Alright, so I am working a modular inverse problem. The problem is "Use the Euclidean algorithm to find the inverse of of 47 modulo 151."

    So I start off with:

    151 = 3 * 47 + 10
    47 = 4 * 10 + 7
    10 = 1 * 7 + 3
    7 = 2 * 3 + 1
    3 = 3 * 1 + 0

    Then I rewrite so I can solve for s and t

    10 = 151 - 3 * 47
    7 = 47 - 4 * 10
    3 = 10 - 1 * 7
    1 = 7 - 2 * 3

    Then I setup to find s and t

    1 = 7 - 2 * 3
    1 = 7 - 2 ( 10 - 1 * 7 )
    1 = 7 - 2 * 10 + 2 * 7
    1 = -2 * 10 + 3 * 7
    1 = -2 * 10 + 3 ( 47 - 4 * 10 )
    1 = -2 * 10 + 3 * 47 + 12 * 10
    1 = 3 * 47 - 14 * 10
    1 = 3 * 47 - 14 (151 - 3 * 47 )
    1 = 3 * 47 - 14 * 151 + 42 * 47
    1 = -14 * 151 + 45 * 47

    s = -14
    t = 45

    So I found this website:
    Modular inversion - Fast mod inverse calculator

    And when I plug in 47 for n and 151 for p

    It tells me the modular inverse is 45.

    So is the modular inverse the same as t? And if not how do I solve for the modular inverse using the Euclidean Algorithm.

    cheers/thanks.

    So you got 47t+151s = 1 . Now reduce this equation \pmod {151}: 47t=1\!\!\!\pmod{151}\Longrightarrow sure t is ALWAYS the inverse !

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    21

    Are you being facetious?

    Quote Originally Posted by tonio View Post
    So you got 47t+151s = 1 . Now reduce this equation \pmod {151}: 47t=1\!\!\!\pmod{151}\Longrightarrow sure t is ALWAYS the inverse !

    Tonio
    I found another website with a modular inverse calculator

    Fast Exponentation Calculator

    and a website that explains how to work out the modular inverse

    Chapter*3.*Modular Arithmetic

    so in the example above the inverse of 15 when the modulus is 26 is going to be 7 right? 7 being the multiplicative inverse of 15 under modulus 26.

    So the correct input into the calculator listed in this post for the problem
    inverse of 15 modulo 26

    x is 15
    n is 26

    yields 7
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: November 25th 2011, 11:53 AM
  2. Modular multiplicative inverse
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 25th 2010, 05:26 AM
  3. Modular Multiplicative Inverse
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 6th 2009, 12:56 PM
  4. Modular Question
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 3rd 2009, 09:00 AM
  5. Modular Inverse
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 27th 2008, 03:32 PM

Search Tags


/mathhelpforum @mathhelpforum