# Modular inverse

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

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

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

## Finding the inverse

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

Then $a^{{-1}}\equiv x\mod {m}$, and also $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 $\phi (m)$, you can also compute the inverses using Euler's theorem, which states that $a^{{\phi (m)}}\equiv 1\mod {m}$. By multiplying both sides of this equation by $a$'s modular inverse, we can deduce that: $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 $m$ is a fixed number in your program (so, you can hardcode a precomputed value of $\phi (m)$), or if $m$ is a prime number, in which case $\phi (m)=m-1$. In general case, however, computing $\phi (m)$ is equivalent to factoring, which is a hard problem, so prefer using the extended GCD algorithm.

## Applications

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

Thus:

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