# Modular Multiplicative Inverse

Printable View

• Oct 2nd 2009, 04:27 AM
Aquafina
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..
• Oct 3rd 2009, 12:43 AM
BobP
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
$\displaystyle 4d\equiv 3\mod(5)),$
and so on.
• Oct 3rd 2009, 09:38 AM
Aquafina
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.
• Oct 5th 2009, 12:22 AM
BobP
$\displaystyle 4d\equiv8\bmod(5)$ says that, on division by $\displaystyle 5$, $\displaystyle 4d$ and $\displaystyle 8$ leave the same remainder, which implies that
$\displaystyle 4d-8=5k$ for some value of $\displaystyle k.$
($\displaystyle 4d=5k_1+r,\quad 8=5k_2+r,$ subtract.)
$\displaystyle d$ and $\displaystyle k$ are integers, so $\displaystyle k$ must contain a factor of 4. Dividing by 4 leads to
$\displaystyle d-2=5l$ (say), which in turn implies that
$\displaystyle d\equiv2\bmod(5).$
• Oct 5th 2009, 06:56 AM
Aquafina
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?
• Oct 5th 2009, 03:50 PM
Bruno J.
It's not really any different than usual division in that sense; dividing by $\displaystyle y$, essentially, is just multiplying by $\displaystyle \frac{1}{y}$. Normally, in arithmetic, to divide $\displaystyle x$ by $\displaystyle y$ you mutiply $\displaystyle x$ by the inverse of $\displaystyle y$, which we denote $\displaystyle 1/y$. So here, to invert 3 modulo 10, you just multiply 3 by its inverse modulo 10, which happens to be 7.
• Oct 6th 2009, 12:56 PM
tonio
Quote:

Originally Posted by Aquafina
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..

-----------------------------------------------------------