Results 1 to 4 of 4

Math Help - modulo inverse

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    modulo inverse

    How do I solve:

    x\equiv 12^{-1} \ (\text{mod} \ 25)

    I know x = 23.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Re: modulo inverse

    12^{-1} is the multiplicative inverse of 12 modulo 25 and satifies the congruence 12x\equiv1\pmod{25}. By inspection, 12\cdot-2=-24\equiv1\pmod{25}. Therefore, x\equiv-2\equiv23\pmod{25}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Re: modulo inverse

    Quote Originally Posted by melese View Post
    12^{-1} is the multiplicative inverse of 12 modulo 25 and satifies the congruence 12x\equiv1\pmod{25}. By inspection, 12\cdot-2=-24\equiv1\pmod{25}. Therefore, x\equiv-2\equiv23\pmod{25}.
    Why does negative 2 represent 12^{-1}?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,153
    Thanks
    591

    Re: modulo inverse

    whatever 12^(-1) (mod 25) is, it should be the case that 12(12^(-1)) = 1 (mod 25).

    12(-2) = -24 = 1 - 25, so 12(-2) = 1 (mod 25).

    similarly -2 = 23 (mod 25).

    to explain properly why this works, note that gcd(12, 25) = 1.

    this means we can find integers r,s with 12r + 25s = 1.

    this equality still holds mod 25, so:

    12r = 1 mod 25.

    in this case, it is easy to see that r = -2 and s = 1 will work:

    12(-2) + 25(1) = -24 + 25 = 1.

    so 12(-2) = 1 (mod 25), but also:

    (12)(-2) (mod 25) = (12 (mod 25))(-2 (mod 25)) = (12)(23).

    but if we didn't guess r = -2, and s = 1 right off the bat, we could have calculated them like so:

    25 = 12(2) + 1, (by the division algorithm)

    so 1 = 25 - 12(2) = 25(1) + 12(-2) (running the division algorithm backwards,

    to find the remainder (the gcd in this case) in terms of the numbers we're taking the gcd of).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. inverse of 4 modulo 9
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 17th 2009, 06:40 AM
  2. inverse of modulo
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 22nd 2009, 07:03 PM
  3. Inverse Modulo
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 9th 2009, 04:46 PM
  4. Inverse of a modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 3rd 2008, 11:00 AM
  5. inverse modulo
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 15th 2008, 01:31 PM

/mathhelpforum @mathhelpforum