# How to find Multiplicative Inverse of a number modulo M?

What is Multiplicative Inverse? What is Modular Multiplicative Inverse? How to find Modular Multiplicative Inverse? How to find Multiplicative Inverse of a number modulo M i.e. under M? How to find Modular Multiplicative Inverse in an efficient way? We will discuss and implement all of the above problems in Python and C++

January 28, 2017 - 14 minute read -

## What is Multiplicative Inverse?

Multiplicative Inverse of a number A is another number B, such that A x B equals 1. Multiplicative Inverse of a number A is denoted as A-1, and A x A-1 = 1. For example: multiplicative inverse of 3 is 1/3 because 3 x 1/3 = 1.

## What is Modular Multiplicative Inverse?

In modular arithmetic, we don’t have the `/` division operator. However, we have `%` modulo operator which helps in finding Modular Multiplicative Inverse.

Modular Multiplicative Inverse of a number A in the range M is defined as a number B such that (A x B) % M = 1.

Important points to note:

• Modulo inverse exists only for numbers that are co-prime to M.
• If (A x B) % M = 1, then B lies in the range [0, M-1]

## How to find Multiplicative Inverse of a number modulo M i.e. under M?

We know for a fact that, if multiplicative inverse for a number exists then it lies in the range [0, M-1]. So the basic approach to find multiplicative inverse of A under M is:

• Iterate from `0` to `M-1`, call it `i`
• Check if `(A x i) % M` equals `1`
• If yes, then we have `i` as multiplicative inverse of `A` under `M`

## Brute Force Python Code to find Multiplicative Inverse of a number modulo M - O(M)

The above implementation is a brute force approach to find Modular Multiplicative Inverse. Time Complexity is O(M), where M is the range under which we are looking for the multiplicative inverse. However, this method fails to produce results when M is as large as a billion, say 1000000000. Try out using A = 23 and M = 1000000007. Can we do any better?

## Modular Multiplicative Inverse using Extended Euclid’s Algorithm

We will not get deeper into Extended Euclid’s Algorithm right now, however, let’s accept the fact that it finds `x` and `y` such that `a*x + b*y = gcd(a, b)`. Let’s see how we can use it to find Multiplicative Inverse of a number A modulo M, assuming that A and M are co-prime.

• Using A in place of `a` and M in place of `b` in the equation, we have `A*x + M*y = gcd(A, M)`.
• We know Greatest Common Divisor (GCD) of two co-prime numbers is 1. So now we have, `A*x + M*y = 1`
• Taking modulo with M on both sides we have, `(A*x) % M + (M*y) % M = 1 % M`, which results into `(A*x) % M = 1 % M` (because `(M*y) % M` is 0)
• Voila, what do we call `x` if `(A*x) % M = 1 % M`? `x` is our answer, i.e. multiplicative inverse of A under M.

Now, for any two numbers `a` and `b` Extended Euclid’s Algorithm finds three things: `gcd(a, b)`, `x` and `y` such that `a*x + b*y = gcd(a, b)`. Please consider reading about Extended Euclid’s Algorithm1.

### Python Implementation - O(log M)

Time Complexity of the above approach is O(log(A) + log(M)).

### C++ Implementation - O(log M)

At times, Extended Euclid’s algorithm is hard to understand. There is one easy way to find multiplicative inverse of a number A under M. We can use fast power algorithm for that.

## Modular Multiplicative Inverse using Fast Power Algorithm

Pierre de Fermat2 once stated that, if M is prime then, A-1 = AM-2 % M. Now from Fast Power Algorithm, we can find AM-2 % M in O(log M) time.

### C++ Implementation - O(sqrt(N))

Note that this method works when M is a prime number. Time Complexity of the above algorithm is also O(log M).

References:

• [1]: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
• [2]: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem