Math Help - Modular Multiplicative Inverse

1. 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.

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..

2. Because the preceding numbers are all divisible by 5,
1 and 4d+3 must leave the same remainder when divided by 5.
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.

3. 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.

4. $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).$

5. 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?

6. 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.

7. 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.

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..
-----------------------------------------------------------