# Modular inverse

The inverse of a number ${\displaystyle a}$ modulo ${\displaystyle m}$ is a number ${\displaystyle x}$ such that ${\displaystyle ax\equiv 1\mod {m}}$. It exists (and is unique if exists) if and only ${\displaystyle a}$ and ${\displaystyle m}$ are relatively prime (that is, ${\displaystyle \gcd(a,m)=1}$). In particular, if ${\displaystyle m}$ is a prime, every non-zero element of ${\displaystyle Z_{m}}$ has an inverse (thus making it an algebraic structure known as field).

Conventionally, the mathematical notation used for inverses is ${\displaystyle a^{-1}\mod {m}}$.

In modular arithmetic the inverse of ${\displaystyle a}$ is analogous to the number ${\displaystyle 1/a}$ in usual real-number arithmetic. If you have a product ${\displaystyle c=ab}$, and one of the factors has an inverse, you can get the other factor by multiplying the product by that inverse: ${\displaystyle a=cb^{-1}\mod {m}}$. Thus you can perform division in ring ${\displaystyle Z_{m}}$.

## Finding the inverse

We can rewrite the defining equation of modular inverses as an equivalent linear diophantine equation: ${\displaystyle ax+my=1}$. This equation has a solution whenever ${\displaystyle \gcd(a,m)=1}$, and we can find such solution ${\displaystyle (x,y)}$ by means of the extended Euclidean algorithm.

Then ${\displaystyle a^{-1}\equiv x\mod {m}}$, and also ${\displaystyle m^{-1}\equiv y\mod {a}}$.

The following Python code implements this algorithm.

# Iterative Algorithm (xgcd)
def iterative_egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q,r = b//a,b%a; m,n = x-u*q,y-v*q # use x//y for floor "floor division"
b,a, x,y, u,v = a,r, u,v, m,n
return b, x, y

# Recursive Algorithm
def recursive_egcd(a, b):
"""Returns a triple (g, x, y), such that ax + by = g = gcd(a,b).
Assumes a, b >= 0, and that at least one of them is > 0.
Bounds on output values: |x|, |y| <= max(a, b)."""
if a == 0:
return (b, 0, 1)
else:
g, y, x = recursive_egcd(b % a, a)
return (g, x - (b // a) * y, y)

egcd = iterative_egcd  # or recursive_egcd(a, m)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
return None
else:
return x % m


## Alternative algorithm

If you happen to know ${\displaystyle \phi (m)}$, you can also compute the inverses using Euler's theorem, which states that ${\displaystyle a^{\phi (m)}\equiv 1\mod {m}}$. By multiplying both sides of this equation by ${\displaystyle a}$'s modular inverse, we can deduce that: ${\displaystyle a^{-1}\equiv a^{\phi (m)-1}\mod {m}}$.

And so you can utilize repeated squaring algorithm to quickly find the inverse.

This algorithm can be useful if ${\displaystyle m}$ is a fixed number in your program (so, you can hardcode a precomputed value of ${\displaystyle \phi (m)}$), or if ${\displaystyle m}$ is a prime number, in which case ${\displaystyle \phi (m)=m-1}$. In general case, however, computing ${\displaystyle \phi (m)}$ is equivalent to factoring, which is a hard problem, so prefer using the extended GCD algorithm.

## Applications

Suppose we need to calculate ${\displaystyle {\frac {a}{b}}\mod {p}}$. If ${\displaystyle b}$ and ${\displaystyle p}$ are co-primes (or if one of them is a prime), then we can calculate the modular inverse ${\displaystyle b'}$ of ${\displaystyle b}$.

Thus:

${\displaystyle {\frac {a}{b}}\mod {P}\equiv ab'\mod {P}}$