Does some standard Python module contain a function to compute modular multiplicative inverse of a number, i.e. a number `y = invmod(x, p)` such that `x*y == 1 (mod p)`? Google doesn’t seem to give any good hints on this.

Of course, one can come up with home-brewed 10-liner of extended Euclidean algorithm, but why reinvent the wheel.

For example, Java’s `BigInteger` has `modInverse` method. Doesn’t Python have something similar?

### Python 3.8+

``````y = pow(x, -1, p)
``````

### Python 3.7 and earlier

Maybe someone will find this useful (from wikibooks):

``````def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
``````

If your modulus is prime (you call it `p`) then you may simply compute:

``````y = x**(p-2) mod p  # Pseudocode
``````

Or in Python proper:

``````y = pow(x, p-2, p)
``````

Here is someone who has implemented some number theory capabilities in Python: http://www.math.umbc.edu/~campbell/Computers/Python/numbthy.html

Here is an example done at the prompt:

``````m = 1000000007
x = 1234567
y = pow(x,m-2,m)
y
989145189L
x*y
1221166008548163L
x*y % m
1L
``````

You might also want to look at the gmpy module. It is an interface between Python and the GMP multiple-precision library. gmpy provides an invert function that does exactly what you need:

``````>>> import gmpy
>>> gmpy.invert(1234567, 1000000007)
mpz(989145189)
``````

As noted by @hyh , the `gmpy.invert()` returns 0 if the inverse does not exist. That matches the behavior of GMP’s `mpz_invert()` function. `gmpy.divm(a, b, m)` provides a general solution to `a=bx (mod m)`.

``````>>> gmpy.divm(1, 1234567, 1000000007)
mpz(989145189)
>>> gmpy.divm(1, 0, 5)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: not invertible
>>> gmpy.divm(1, 4, 8)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: not invertible
>>> gmpy.divm(1, 4, 9)
mpz(7)
``````

`divm()` will return a solution when `gcd(b,m) == 1` and raises an exception when the multiplicative inverse does not exist.

Disclaimer: I’m the current maintainer of the gmpy library.

gmpy2 now properly raises an exception when the inverse does not exists:

``````>>> import gmpy2

>>> gmpy2.invert(0,5)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: invert() no inverse exists
``````

As of 3.8 pythons pow() function can take a modulus and a negative integer. See here. Their case for how to use it is

``````>>> pow(38, -1, 97)
23
>>> 23 * 38 % 97 == 1
True
``````

Here is a one-liner for CodeFights; it is one of the shortest solutions:

``````MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1]
``````

It will return `-1` if `A` has no multiplicative inverse in `n`.

Usage:

``````MMI(23, 99) # returns 56
MMI(18, 24) # return -1
``````

The solution uses the Extended Euclidean Algorithm.

Sympy, a python module for symbolic mathematics, has a built-in modular inverse function if you don’t want to implement your own (or if you’re using Sympy already):

``````from sympy import mod_inverse

mod_inverse(11, 35) # returns 16
mod_inverse(15, 35) # raises ValueError: 'inverse of 15 (mod 35) does not exist'
``````

This doesn’t seem to be documented on the Sympy website, but here’s the docstring: Sympy mod_inverse docstring on Github

Here is a concise 1-liner that does it, without using any external libraries.

``````# Given 0<a<b, returns the unique c such that 0<c<b and a*c == gcd(a,b) (mod b).
# In particular, if a,b are relatively prime, returns the inverse of a modulo b.
def invmod(a,b): return 0 if a==0 else 1 if b%a==0 else b - invmod(b%a,a)*b//a
``````

Note that this is really just egcd, streamlined to return only the single coefficient of interest.

I try different solutions from this thread and in the end I use this one:

``````def egcd(a, b):
lastremainder, remainder = abs(a), abs(b)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient*x, x
y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if a < 0 else 1), lasty * (-1 if b < 0 else 1)

def modinv(a, m):
g, x, y = self.egcd(a, m)
if g != 1:
raise ValueError('modinv for {} does not exist'.format(a))
return x % m
``````

Modular_inverse in Python

Here is my code, it might be sloppy but it seems to work for me anyway.

``````# a is the number you want the inverse for
# b is the modulus

def mod_inverse(a, b):
r = -1
B = b
A = a
eq_set = []
full_set = []
mod_set = []

#euclid's algorithm
while r!=1 and r!=0:
r = b%a
q = b//a
eq_set = [r, b, a, q*-1]
b = a
a = r
full_set.append(eq_set)

for i in range(0, 4):
mod_set.append(full_set[-1][i])

mod_set.insert(2, 1)
counter = 0

#extended euclid's algorithm
for i in range(1, len(full_set)):
if counter%2 == 0:
mod_set[2] = full_set[-1*(i+1)][3]*mod_set[4]+mod_set[2]
mod_set[3] = full_set[-1*(i+1)][1]

elif counter%2 != 0:
mod_set[4] = full_set[-1*(i+1)][3]*mod_set[2]+mod_set[4]
mod_set[1] = full_set[-1*(i+1)][1]

counter += 1

if mod_set[3] == B:
return mod_set[2]%B
return mod_set[4]%B
``````

The code above will not run in python3 and is less efficient compared to the GCD variants. However, this code is very transparent. It triggered me to create a more compact version:

``````def imod(a, n):
c = 1
while (c % a > 0):
c += n
return c // a
``````

from the cpython implementation source code:

``````def invmod(a, n):
b, c = 1, 0
while n:
q, r = divmod(a, n)
a, b, c, n = n, c, b - q*c, r
# at this point a is the gcd of the original inputs
if a == 1:
return b
raise ValueError("Not invertible")
``````

according to the comment above this code, it can return small negative values, so you could potentially check if negative and add n when negative before returning b.

To figure out the modular multiplicative inverse I recommend using the Extended Euclidean Algorithm like this:

``````def multiplicative_inverse(a, b):
origA = a
X = 0
prevX = 1
Y = 1
prevY = 0
while b != 0:
temp = b
quotient = a/b
b = a%b
a = temp
temp = X
a = prevX - quotient * X
prevX = temp
temp = Y
Y = prevY - quotient * Y
prevY = temp

return origA + prevY
``````

Well, I don’t have a function in python but I have a function in C which you can easily convert to python, in the below c function extended euclidian algorithm is used to calculate inverse mod.

``````int imod(int a,int n){
int c,i=1;
while(1){
c = n * i + 1;
if(c%a==0){
c = c/a;
break;
}
i++;
}
return c;}
``````

Python Function

``````def imod(a,n):
i=1
while True:
c = n * i + 1;
if(c%a==0):
c = c/a
break;
i = i+1

return c
``````

Reference to the above C function is taken from the following link C program to find Modular Multiplicative Inverse of two Relatively Prime Numbers