Modular Multiplicative Inverse

Using Fermat’s Little Theorem

To calculate (A/B)%m we need modular multiplicative inverse of B. 
(A/B)%m = (A%m * B^-1%m) %m

              = (A%m * modular_multiplicative_inverse(B) ) %m.

Fermat’s little theorem states that if m is a prime and a is an integer co-prime to m, then a^p − 1 will be evenly divisible by m. That is  or  Here’s a sample C++ code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

/* This function calculates (a^b)%MOD */ int pow(int a, int b, int MOD) { int x = 1, y = a;     while(b > 0) {         if(b%2 == 1) {             x=(x*y);             if(x>MOD) x%=MOD;         }         y = (y*y);         if(y>MOD) y%=MOD;         b /= 2;     }     return x; } int modInverse(int a, int m) {     return pow(a,m-2,m); }

The time complexity of the above codes is O(log(m)).