# Calculate Modular Multiplicative Inverse in Python

Suraj Joshi Dec 24, 2021 Aug 01, 2021 Python Python Math

If we have two numbers `a` and `m`, then the modular multiplicative inverse of `a` is `x` under modulo `m` if:

``````a * x % m = 1
``````

In this case, the multiplicative inverse exists only if `a` and `m` are relatively prime i.e. if the greatest common divisor of both `a` and `m` is `1`.

The value of `x` can range from `1` to `m-1`.

## Modular Multiplicative Inverse Using the Naive Iterative Approach

Suppose we need to find the multiplicative inverse of `a` under modulo `m`. If the modulo multiplicative inverse exists, its value can range from `1` to `m-1`., Hence, we iterate through this range and check the condition for modulo multiplicative inverse. If any number within the range satisfies the condition, we have the number as modulo multiplicative inverse.

``````def find_mod_inv(a,m):

for x in range(1,m):
if((a%m)*(x%m) % m==1):
return x
raise Exception('The modular inverse does not exist.')

a = 13
m = 22

try:
res=find_mod_inv(a,m)
print("The required modular inverse is: "+ str(res))

except:
print('The modular inverse does not exist.')
``````

Output:

``````The required modular inverse is: 17
``````

Here, we have a function named `find_mod_inv` which takes `a` and `m` as input and returns the multiplicative inverse of `a` under modulo `m`.

If the number `a` does not have a multiplicative inverse of `a` under modulo `m`, it will raise an exception.

From the example above, we can see the modular multiplicative inverse of `13` under modulo `22` is `17`.

## Modular Multiplicative Inverse Using `pow()` Builtin Function

We can also use the built-in function `pow()` from Python to compute the modular multiplicative inverse of a number.

``````a=38
m=97
res = pow(a, m-2, m)
print("The required modular inverse is: "+ str(res))
``````

Output:

``````The required modular inverse is: 23
``````

To calculate the modulo multiplicative inverse using the `pow()` method, the first parameter to the `pow()` method will be the number whose modulo inverse is to be found, the second parameter will be the order of modulo subtracted by 2 and the last parameter will be the order of modulo.

However, for `Python 3.8` and above, we can replace the second argument with `-1`.

``````a=38
m=97
res = pow(a, -1, m)
print("The required modular inverse is: "+ str(res))
``````

output:

``````The required modular inverse is: 23
``````
Author: Suraj Joshi

Suraj Joshi is a backend software engineer at Matrice.ai.