Results 1 to 4 of 4

Math Help - Modular multiplicative inverse

  1. #1
    Pan
    Pan is offline
    Newbie
    Joined
    May 2008
    Posts
    10

    Modular multiplicative inverse

    I don't quite understand this concept, or how to write it down algebraically (not sure what the triple equals thing means).

    So let's say I want to find the multiplicative inverse of 3 \mod{11}. Am I right in thinking that I am looking for a number that when multiplied by 3, and then divided by 11, I will get remainder 1. The reason I struggle writing this down is because the quotient is irrelevant.

    Anyway, to work this out in my head, I would use trial and error:
    1 \times 3 \mod{11} = 3
    2 \times 3 \mod{11} = 6
    3 \times 3 \mod{11} = 9
    4 \times 3 \mod{11} = 1 because 12/11 is 1 remainder 1

    So the answer is 4.

    Presuming what I have done so far is right, I don't understand why Wikipedia says 15 is also an answer? 15*4 = 60, and 60/11 is 5 r5, NOT r1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Pan View Post
    I don't quite understand this concept, or how to write it down algebraically (not sure what the triple equals thing means).

    So let's say I want to find the multiplicative inverse of 3 \mod{11}. Am I right in thinking that I am looking for a number that when multiplied by 3, and then divided by 11, I will get remainder 1. The reason I struggle writing this down is because the quotient is irrelevant.

    Anyway, to work this out in my head, I would use trial and error:
    1 \times 3 \mod{11} = 3
    2 \times 3 \mod{11} = 6
    3 \times 3 \mod{11} = 9
    4 \times 3 \mod{11} = 1 because 12/11 is 1 remainder 1

    So the answer is 4.

    Presuming what I have done so far is right, I don't understand why Wikipedia says 15 is also an answer? 15*4 = 60, and 60/11 is 5 r5, NOT r1.

    You are right in your calculations but you got confused with 15: it is the inverse of 3, NOT of 4! And indeed, 15*3=45 = 11*4+1.

    Of course, 15=4 modulo 11, so we usually use 4 instead of 15 when working modulo 11.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Pan
    Pan is offline
    Newbie
    Joined
    May 2008
    Posts
    10
    Oh thanks... I really get confused when trying to think of modular arithmetic.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,696
    Thanks
    1467
    There are two ways of thinking about modular arithmetic (mod 11, say).
    1) Think of the "numbers" as only 0 to 10.
    2) Think of the "numbers" as sets of numbers which have the same remainder when divided by 10.

    In the first case, only "4" is the multiplicative inverse of 3 because 3*4= 12= 11+ 1 so 3*4= 1 (mod 11). "15" would not qualify because it is not between 0 and 10.

    In the second case, the multiplicative inverse of "3" (representing the set {3, 14, -8, 25, -19, ...}) is the set {4, 15, -7, 26, -18, ...}. If we think of each set as "represented" by the smallest positive number in the set, we are back to (1).
    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. multiplicative inverse
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 23rd 2010, 01:31 PM
  3. Multiplicative Inverse
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 4th 2009, 06:47 AM
  4. Modular Multiplicative Inverse
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 6th 2009, 12:56 PM
  5. Multiplicative Inverse?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: December 27th 2007, 10:43 AM

Search Tags


/mathhelpforum @mathhelpforum