Modular Multiplicative Inverse

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 = AN-2 % N

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