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