Results 1 to 7 of 7

Math Help - Modular Multiplicative Inverse

  1. #1
    Member
    Joined
    Apr 2009
    Posts
    190

    Modular Multiplicative Inverse

    Hi I do not understand the idea of Modular Multiplicative Inverse at all. I have tried reading up on modular arithmetic for a day, but I still do not understand it.

    I had the following question, which is a past olympiad question:

    N is a 4 digit number wich doesnt end in a 0, and R(N) is a 4 digit integer obtained by reversing the digits of N. So R(1997) = 7991

    Determine all such integers N for which R(N) = 4N + 3.


    The answer is 1997 only. Below is the solution:

    N = 1000a + 100b + 10c + d

    Since R(N) is odd, a is odd. Also, 4N + 3 is 4 digits so a<3.

    R(N) = 4N + 3

    so:

    1000d + 100c + 10b + 1 = 4000 + 400b + 40c + 4d + 3

    "now working modulo 5, we see 4d=3(mod 5) so d=2(mod 5)."

    I dont understand where this comes from... The equals signs here actually should be 3 lines, so ignore that.

    So d = 2 or d = 7 etc..
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2009
    Posts
    658
    Thanks
    131
    Because the preceding numbers are all divisible by 5,
    1 and 4d+3 must leave the same remainder when divided by 5.
    Adding 2 to both,
    3 and 4d+5 must leave the same remainder when divided by 5, so
    3 and 4d must leave the same remainder when divided by 5, (formally
    4d\equiv 3\mod(5)),
    and so on.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2009
    Posts
    190
    thank you.

    Now for the next bit, how do you get:

    d = 2 (mod 5) (the multiplication inverse bit to reduce the equation)

    this example is a bit of common sense i get now, but could you please explain how to divide in modular arithmetic basically.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2009
    Posts
    658
    Thanks
    131
    4d\equiv8\bmod(5) says that, on division by 5, 4d and 8 leave the same remainder, which implies that
    4d-8=5k for some value of k.
    ( 4d=5k_1+r,\quad 8=5k_2+r, subtract.)
    d and k are integers, so k must contain a factor of 4. Dividing by 4 leads to
    d-2=5l (say), which in turn implies that
    d\equiv2\bmod(5).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2009
    Posts
    190
    Thanks. In my book of number theory, this is what it said about dividing:

    When working modulo 10, the numbers 0,2,4,6,8 and 5 dont have multiplicative inverses, but 3x7=1 mod10, 9x9 = 1 mod10, and 1x1 = 1 mod 10.

    So you can divide by 3 by multiplying by 7, and vice versa. And you can divide by 9 = -1 mod 10 by multiplying by 9.

    What does this all mean? Whats with the whole dividing by a number, say x, by multiplying by another number, say y?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    It's not really any different than usual division in that sense; dividing by y, essentially, is just multiplying by \frac{1}{y}. Normally, in arithmetic, to divide x by y you mutiply x by the inverse of y, which we denote 1/y. So here, to invert 3 modulo 10, you just multiply 3 by its inverse modulo 10, which happens to be 7.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Aquafina View Post
    Hi I do not understand the idea of Modular Multiplicative Inverse at all. I have tried reading up on modular arithmetic for a day, but I still do not understand it.

    I had the following question, which is a past olympiad question:

    N is a 4 digit number wich doesnt end in a 0, and R(N) is a 4 digit integer obtained by reversing the digits of N. So R(1997) = 7991

    Determine all such integers N for which R(N) = 4N + 3.

    The answer is 1997 only. Below is the solution:

    N = 1000a + 100b + 10c + d

    Since R(N) is odd, a is odd. Also, 4N + 3 is 4 digits so a<3.

    R(N) = 4N + 3

    so:

    1000d + 100c + 10b + 1 = 4000 + 400b + 40c + 4d + 3

    "now working modulo 5, we see 4d=3(mod 5) so d=2(mod 5)."

    I dont understand where this comes from... The equals signs here actually should be 3 lines, so ignore that.


    1000 is 0 mod 5 since its residue upon dividing it by 5 is zero, and etc.


    So in 1000d + 100c + 10b + 1 = 4000 + 400b + 40c + 4d + 3 , if we work modulo 5 (i.e., if we take all the residues of the different numbers when divided by 5), we get 1 = 4d + 3 ==> 4d = -2 = 3 (mod 5) since -2 = 3 (mod 5) (this means: when divided by 5, both -2 and 3 give the same residue, namely 3)

    Since the multiplicative in verse of 4 modulo 5 is 4 (since 4*4 = 16 = 1 (mod 5), we get that 4d = 3 (mod 5) ==> d = 4^(-1)*3 (mod 5) = 4*3 (mod 5) = 2 (mod 5).

    Now, if you never have studied modular arithmetic then the above will probably way too hard for you. Grab some algebra book (Dummit and Foote, Hungerford, Fraleigh, etc) and try more than just 1 day...or wait until you get into some university and learn this.

    Tonio

    So d = 2 or d = 7 etc..
    -----------------------------------------------------------
    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. multiplicative inverse
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 23rd 2010, 01:31 PM
  4. Multiplicative Inverse
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 4th 2009, 06:47 AM
  5. Multiplicative inverse
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 14th 2006, 01:53 PM

Search Tags


/mathhelpforum @mathhelpforum