 New update is available. Click here to update.
Last Updated: Mar 1, 2023

# Multiplicative Inverse  0 upvotes

## Introduction

In modular multiplicative inverse, two numbers are provided, ‘a’ and ‘m’, such that the  given condition is satisfied:  The value of ‘x’ lies in the range of {1, 2, 3, …, m - 1}.

Note: ‘x’ can never become 0. As a * 0 mod ‘m’ can never be 1.

If you know the values of ‘a’ and ‘m’, how can you figure out the value of ‘x’? Come, let’s figure it out in detail.

### Working:

So, through this approach, we are looking for an integer solution for ‘x’. Let’s take an example, In other words, what we need to multiply with 5 and divide the result by 7, such that 3 becomes the remainder

One way to solve for x is the brute force approach. In the brute force approach, values from 1 to (m - 1) are plotted in the equation and are checked if the given criterion is fulfilled. In the above example, values from 1 to 6 are plotted and checked to see if they produce the result we are looking for.

The multiplicative inverse of a mod m exists if gcd(a,m) is 1 or a and m are relatively prime.

If a=5 and m=7, the output will be 3. Since 5 * 3 mod 713 is modulo inverse of 5(under 7).

### Naive Approach:

Output:

#### Time Complexity: O(m)

In the naive approach, we check for every number from 1 to m, so, the time complexity is O(m).

#### Space Complexity: O(1)

As constant space is used in this approach hence, the space complexity is O(1).

### Efficient Approach:

This approach can only work if ‘a’ and ‘m’ are coprime to each other, i.e., gcd(a, m) = 1. The main idea is based on an extended Euclid algorithm. The idea is to take two integers a and b and find their gcd as well as the value of x and y. To simplify the equation further, we put b = m. Since we already know that the gcd of a and m is prime, we can use the gcd value as 1.

Taking modulo in both sides, the equation becomes:  The second term can be easily removed as for any integer y, taking mod with m is always zero. So, the final equation looks like this:

x can be found out using the Extended Euclid Algorithm, which is the multiplicative inverse of a. ### Recursive Approach using Extended Euclid’s Algorithm:

Output:

#### Time Complexity: O(log m)

The time complexity of this approach is O(log m) as for every recursive call we are reducing ‘a’ by continuously doing mod with b.

#### Space complexity: O(1)

As constant space is used, the space complexity is O(1).

### Iterative Approach using Extended Euclid’s Algorithm:

The idea is very similar as we applied for the recursive way of the modular multiplicative inverse. Just the difference lies in the implementation part, in the above example we applied a recursive approach, now we will be looking for the iterative approach.

Implementation in C++:

Output:

#### Time Complexity: O(log m)

The time complexity of this approach is O(log m) as for every recursive call we are reducing ‘a’ by continuously doing mod with b.

#### Space Complexity: O(1)

As constant space is used, the space complexity is O(1).

### III: Fermat’s little theorem approach:

This approach is based on Fermat’s little theorem. This approach can only work if m is prime. Multiplying by a-1on both sides we get, Output:

#### Time Complexity: O(log m)

The time complexity of this approach is O(log m) as for every recursive call we are reducing ‘a’ by continuously doing mod with b.

#### Space Complexity: O(1)

As constant space is used, space complexity for this approach is O(1).

What is the output of 3 mod 11?

The output of 3 mod 11 is 3.

What is an inverse?

The inverse is a way of representing a number in such a way that, when multiplied with its inverse, it gives 1 as result.

Eg: 5 X 1 / 5 = 1.

How do you do modular multiplicative inverse?

The modular multiplicative inverse is done by the “Chinese remainder theorem”. According to the Chinese remainder theorem, if one knows the remainder of the Euclidean division of an integer ’n’, then the remainder of the division of ‘n’ by the product of the integers can be uniquely determined under the condition that divisors are pairwise coprime

What is the easiest way to find a multiplicative inverse?

For any natural number x(0, 1, 2, 3, …), the multiplicative inverse is 1/x. For example, the multiplicative inverse of 7 is 1/7.

### Key Takeaways:

In this article we learned about modular multiplicative inverse and various approaches to solving it, starting from the naive to efficient approach. But this isn’t the end. Go on top