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