Results 1 to 6 of 6

Math Help - Inverse of an integer modulo m

  1. #1
    Newbie
    Joined
    Nov 2006
    Posts
    7

    Inverse of an integer modulo m

    Hi, I have a test tomorrow, and I have been trying for a very long time to figure out how to do this. Thank you in advance for any help you can give me.

    This is the question:
    Find the inverse of 5 modulo 16.

    Please explain how to do this in steps. I already know the answer, I just don't know how to get it.
    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by lisaak View Post
    Hi, I have a test tomorrow, and I have been trying for a very long time to figure out how to do this. Thank you in advance for any help you can give me.

    This is the question:
    Find the inverse of 5 modulo 16.

    Please explain how to do this in steps. I already know the answer, I just don't know how to get it.
    Thanks
    First of all, 5 and 16 are relatively prime so 5 does have a multiplicative inverse mod 16.

    By definition, you need to find the integer value of a such that 5a = 1 modulo 16.

    One quick way here is to see that a = \frac{16n+1}{5} where n is an integer. It's not hard to see that n = 4 works and so a = 13.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by mr fantastic View Post
    First of all, 5 and 16 are relatively prime so 5 does have a multiplicative inverse mod 16.

    By definition, you need to find the integer value of a such that 5a = 1 modulo 16.

    One quick way here is to see that a = \frac{16n+1}{5} where n is an integer. It's not hard to see that n = 4 works and so a = 13.
    And I guess you saw that n = -1 works too => a = -3. The multipicative inverse is not unique.

    A link you might find helpful is this.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2006
    Posts
    7
    Okay, so what if the numbers are larger? How do I find the inverse of say 40 mod 81? Because this one is not easy to see as in the previous example.

    a= (81n+1)/40
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2006
    Posts
    7
    alright, here is what I'm thinking:
    since 40x is congruent to 1 mod 81
    40x-1=81y (y in Z)
    40x+81z=1 (where z is -y)

    So working the Euclidean Algorithm backwards I can express the equation as 1=81-40*2

    So, 40(-2) is congruent to 1 mod 81

    81+(-2)=79
    Thus, 79 is the multiplicative inverse.

    Does this make sense?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by lisaak View Post
    alright, here is what I'm thinking:
    since 40x is congruent to 1 mod 81
    40x-1=81y (y in Z)
    40x+81z=1 (where z is -y)

    So working the Euclidean Algorithm backwards I can express the equation as 1=81-40*2

    So, 40(-2) is congruent to 1 mod 81

    81+(-2)=79
    Thus, 79 is the multiplicative inverse.

    Does this make sense?
    Well you got a correct answer so it looks good to me!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] inverse in modulo 26
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 9th 2011, 02:52 PM
  2. integer modulo 4 vectors
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 30th 2010, 04:00 PM
  3. inverse of 4 modulo 9
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 17th 2009, 07:40 AM
  4. Inverse Modulo
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 9th 2009, 05:46 PM
  5. (n) inverse modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 21st 2009, 11:49 AM

Search Tags


/mathhelpforum @mathhelpforum