Let us start with few facts and know importance of this topic. While using mod (**%**) operator,

(a + b) % m = a%m + b%m (a * b) % m = a%m * b%m

But this relation doesn’t satisfy when performing division.

(a / b) % m ≠ a%m / b%m

Being a commonly used operator, this problem has to be overcome. i.e. to apply mod operator on a division operation. **Extended Euclidean algorithm** comes to rescue when b,m are co-primes.

When **b and m are co-primes**, find MI = modular inverse of b over m. This modular inverse can be used to find quotient of division applied to modulus.

i.e

(a / b) % m = a%m * MI%m

Here is the C++ function for finding modular multiplicative inverse using extended euclidean:

int modInv(int b, int m) { int r1 = m,r2 = b; int t1 = 0,t2 = 1; int q,r,t; while(r2 > 0) { q = r1/r2; r = r1 - q*r2; r1= r2; r2= r; t = t1 - q*t2; t1 = t2; t2 = t; } if(r1 == 1) return t1; else { printf("Inverse doesn't exist"); return -1; } }

Inverse doesn’t exist only in the cases when b and m are not coprimes.

**Fermet’s Little Theorem:**

This theorem is saviour to overcome the difficulty in able to remember the Extended Euclidean algorithm. In most of the problems on competitive programming, MOD value is generally a constant prime, usually with a value of 10^9 + 7. Fermet’s Little theorem states that inverse of a number ‘A’ over mod ‘N’, when N is prime is modPow(A,N-2,N). i.e.

A^{-1}= A^{N-2}% N

Though the value of N is very large, you can always use Modular Exponentiation Algorithm to solve it efficiently.