We will have a simple background review of modular arithmetic. It will consist of two concepts. 1.What is modular arithmetic. 2. Inverse modular arithmetic.

**1. What is modular arithmetic.**

Simplely put, just think of remainders.

10/3=3 remainder means 10mod3=1. 23/4=5 remainder 3 means 23mod4=5

In a more mathatical terms, x=y mod m means (x-y) divides m.

**2. Modular Multiplicative Inverse **

Again, think about elementary arithmetic. The multiplicative inverse of x is 1/x, because x*1/x=1

In modular arithmetic, multiplicative inverse is defined by

If x is the multiplicative inverse of a mod m, then ax =1mod m, in other words, (ax-1) divides m.

a has a multicative inverse if gcd (a, m)=1, (gcd stands for greatest common divisor, gcd(a,m) =1 mean a and m are relatively prime to each other)

I would like to think about it this way, a * ? = (a multiple of m) +1

For example, what is the multiplicative inverse of 4 mod 27 ?

4 * ? = (a multiple of 27) +1

4 * 7 = 1*27 +1

so 4^-1 mod 27 = 7