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.

### Like this:

Like Loading...