# Calculate Modular Multiplicative Inverse in Python

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 and `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
``````
Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

## Related Article - Python Math

• Square Root in Python
• Calculate the Inverse Tangent in Python