## Modular Multiplicative Inverse

The modular multiplicative inverse of an integer a modulo m is an integer x such that

That is, it is the multiplicative inverse in the ring of integers modulo m. This is equivalent to

The multiplicative inverse of a modulo m exists if and only if a and m are coprime (i.e., if gcd(a, m) = 1).

Let’s see various ways to calculate Modular Multiplicative Inverse:

**1. Brute Force**

We can calculate the inverse using a brute force approach where we multiply *a* with all possible values *x* and find a *x* such that Here’s a sample C++ code:

int modInverse(int a, int m) { a %= m; for(int x = 1; x < m; x++) { if((a*x) % m == 1) return x; } }

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

**2. Using Extended Euclidean Algorithm**

We have to find a number x such that a·x = 1 (mod m). This can be written as well as a·x = 1 + m·y, which rearranges into a·x – m·y = 1. Since x and y need not be positive, we can write it as well in the standard form, a·x + m·y = 1.

In number theory, Bézout’s identity for two integers a, b is an expression ax + by = d, where x and y are integers (called Bézout coefficients for (a,b)), such that d is a common divisor of a and b. If d is the greatest common divisor of a and b then Bézout’s identity ax + by = gcd(a,b) can be solved using Extended Euclidean Algorithm.

The Extended Euclidean Algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y (one of which is typically negative) that satisfy Bézout’s identity

ax + by = gcd(a,b). The Extended Euclidean Algorithm is particularly useful when a and b are coprime, since x is the multiplicative inverse of a modulo b, and y is the multiplicative inverse of b modulo a.

We will look at two ways to find the result of Extended Euclidean Algorithm.

**Iterative Method**

This method computes expressions of the form *r _{i}* =

*ax*+

_{i}*by*for the remainder in each step i of the Euclidean algorithm. Each successive number

_{i}*r*can be written as the remainder of the division of the previous two such numbers, which remainder can be expressed using the whole quotient

_{i}*q*of that division as follows:

_{i}By substitution, this gives:

which can be written

The first two values are the initial arguments to the algorithm:

So the coefficients start out as

*x*= 1,

_{1}*y*= 0,

_{1}*x*= 0, and

_{2}*y*= 1, and the others are given by

_{2}The expression for the last non-zero remainder gives the desired results since this method computes every remainder in terms of a and b, as desired.

So the algorithm looks like,

- Apply Euclidean algorithm, and let qn(n starts from 1) be a finite list of quotients in the division.
- Initialize
*x*,_{0}*x*as 1, 0, and_{1}*y*,_{0}*y*as 0,1 respectively._{1}- Then for each i so long as
*q*is defined,_{i} - Compute
*x*=_{i+1}*x*−_{i-1}*q*_{i}*x*_{i} - Compute
*y*=_{i+1}*y*−_{i-1}*q*_{i}*y*_{i} - Repeat the above after incrementing i by 1.

- Then for each i so long as
- The answers are the second-to-last of
*x*and_{n}*y*._{n}

/* This function return the gcd of a and b followed by the pair x and y of equation ax + by = gcd(a,b)*/ pair<int, pair<int, int> > extendedEuclid(int a, int b) { int x = 1, y = 0; int xLast = 0, yLast = 1; int q, r, m, n; while(a != 0) { q = b / a; r = b % a; m = xLast - q * x; n = yLast - q * y; xLast = x, yLast = y; x = m, y = n; b = a, a = r; } return make_pair(b, make_pair(xLast, yLast)); } int modInverse(int a, int m) { return (extendedEuclid(a,m).second.first + m) % m; }

**Recursive Method**

This method attempts to solve the original equation directly, by reducing the dividend and divisor gradually, from the first line to the last line, which can then be substituted with trivial value and work backward to obtain the solution.

Notice that the equation remains unchanged after decomposing the original dividend in terms of the divisor plus a remainder, and then regrouping terms. So the algorithm looks like this:

- If b = 0, the algorithm ends, returning the solution x = 1, y = 0.
- Otherwise:
- Determine the quotient q and remainder r of dividing a by b using the integer division algorithm.
- Then recursively find coefficients s, t such that bs + rt divides both b and r.
- Finally the algorithm returns the solution x = t, and y = s − qt.

Here’s a C++ implementation:

/* This function return the gcd of a and b followed by the pair x and y of equation ax + by = gcd(a,b)*/ pair<int, pair<int, int> > extendedEuclid(int a, int b) { if(a == 0) return make_pair(b, make_pair(0, 1)); pair<int, pair<int, int> > p; p = extendedEuclid(b % a, a); return make_pair(p.first, make_pair(p.second.second - p.second.first*(b/a), p.second.first)); } int modInverse(int a, int m) { return (extendedEuclid(a,m).second.first + m) % m; }

The time complexity of the above codes is *O(log(m) ^{2})*.

**3. Using Fermat’s Little Theorem**

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:

/* 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)).

**4. Using Euler’s Theorem**

Fermat’s Little theorem can only be used if m is a prime. If m is not a prime we can use Euler’s Theorem, which is a generalization of Fermat’s Little theorem. According to Euler’s theorem, if a is coprime to m, that is, gcd(a, m) = 1, then , where where φ(m) is Euler Totient Function. Therefore the modular multiplicative inverse can be found directly: . The problem here is finding φ(m). If we know φ(m), then it is very similar to above method.

Now lets take a little different question. Now suppose you have to calculate the inverse of first n numbers. From above the best we can do is O(n log(m)). Can we do any better? Yes.

We can use sieve to find a factor of composite numbers less than n. So for composite numbers inverse(i) = (inverse(i/factor(i)) * inverse(factor(i))) % m, and we can use either Extended Euclidean Algorithm or Fermat’s Theorem to find inverse for prime numbers. But we can still do better.

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

(a * (m / a) + m % a) mod m = m mod m, or

(a * (m / a) + m % a) mod m = 0, or

(- (m % a)) mod m = (a * (m / a)) mod m.

Dividing both sides by (a * (m % a)), we get

– inverse(a) mod m = ((m/a) * inverse(m % a)) mod m

inverse(a) mod m = (- (m/a) * inverse(m % a)) mod m

Here’s a sample C++ code:

vector<int> inverseArray(int n, int m) { vector<int> modInverse(n + 1,0); modInverse[1] = 1; for(int i = 2; i <= n; i++) { modInverse[i] = (-(m/i) * modInverse[m % i]) % m + m; } return modInverse; }

The time complexity of the above code is O(n).

-fR0DDY

hi! nice blog. :) could u help me in computing multiplicative inverse in java?

sitiDecember 4, 2011 at 10:20 PM

The codes are given in C++. Java should be very similar.

fR0DDYDecember 5, 2011 at 12:17 AM

Excellent Post

MiteshJune 27, 2012 at 6:06 PM

How would we calculate modInverse(a, m)

Where ‘a’ can be as large as 500! and m=1000000007

rnFebruary 8, 2013 at 5:49 PM

first calculate (a!) mod m :

f=1; for(i=1;i<=a;i++) f=(f*i)%m;

then use above algorithm for its inverse.

shahidMarch 8, 2013 at 2:15 AM

Reblogged this on Saurabh Vats.

bit_cracker007May 26, 2013 at 3:53 AM

how to calculate 512 bit (156 decimal digits) numbers using c coding.

navyaJuly 5, 2013 at 8:59 PM

Running your brute force code in Java, I’ve gotten number pairs that have more than 1 multiplicative mod inverse. Is there any significance to that?

EricJuly 10, 2013 at 4:55 AM

Very good blog. Thanks!!

Just a very tiny bit of addition in the last method, the one to compute inverse of all numbers till n. Here, m should be relatively prime (i.e. co-prime) to all the numbers from 2 to n. If this is not the case, then (m%a) = 0, and we cannot divide by (a * (m % a)) and so the equation will break.

PrashantJanuary 19, 2014 at 7:39 PM

Can you tell me how to solve, say, (2n C n) % 1000000006? Since n! in denominator will not be co-prime to 1000000006, we can not apply any of the above method. I heard somewhere that CRT can be used. Can you tell me how?

Thanks!

DhruvApril 14, 2014 at 8:26 PM

This question is a part of http://www.spoj.com/problems/POWPOW/

DhruvApril 14, 2014 at 8:31 PM

Check this blog post:

https://comeoncodeon.wordpress.com/2011/07/31/combination/

fR0DDYApril 15, 2014 at 1:54 PM

“If we have to find nCr mod m(where m is not prime), we can factorize m into primes and then use Chinese Remainder Theorem(CRT) to find nCr mod m”

But my problem is how to use CRT here? I mean, from wikipedia, I got to know that it is used to solve a set of congruence. But, here, we don’t have any congruence in the first place!.

Thanks!

DhruvApril 15, 2014 at 7:16 PM

nice post understood the logic but what does this make_pair function look like ?

hemanthMay 21, 2014 at 12:55 PM

It is a standard C++ function.

http://www.cplusplus.com/reference/utility/make_pair/

fR0DDYMay 21, 2014 at 12:57 PM

thank you very much. very useful post :)

anamzahidAugust 21, 2014 at 12:52 AM

Reblogged this on Anam Zahid and commented:

A very useful post … helps me very much writing key splitter in c++ .. reference code is taking from http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing

anamzahidAugust 21, 2014 at 12:54 AM