# Modular inverse

The inverse of a number *a* modulo *m* is a number *x* such that . 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 .

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* = *a**b*, and one of the factors has an inverse, you can get the other factor by multiplying the product by that inverse: . Thus you can perform division in ring *Z*_{m}.

## [edit] Finding the inverse

We can rewrite the defining equation of modular inverses as an equivalent linear diophantine equation: *a**x* + *m**y* = 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 , and also .

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

## [edit] Alternative algorithm

If you happen to know φ(*m*), you can also compute the inverses using Euler's theorem, which states that . By multiplying both sides of this equation by *a*'s modular inverse, we can deduce that: .

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 φ(*m*)), or if *m* is a prime number, in which case φ(*m*) = *m* - 1. In general case, however, computing φ(*m*) is equivalent to factoring, which is a hard problem, so prefer using the extended GCD algorithm.

## [edit] Applications

Suppose we need to calculate . 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: