Finding a Modular Inverse of an Integer

A modular multiplicative inverse of an integer $a$ under modulo $m$ is an integer $b$ such that

$ab \equiv 1 \ (\textrm{mod} \ m)$.

$a$ and $b$ must be coprime, meaning

$\textrm{gcd}(ab) = 1$.

A common way of finding a modular multiplicative inverse of an integer is to use the extended Euclidean algorithm. To demonstrate this, let’s find a modular multiplicative inverse of 217 under modulo 32.

Pick the larger of the two numbers (217) and, using Euclidean division, divide it by the smaller one (32). Repeat this for the divisor (32) and the remainder obtained (25). Continue until you get a remainder of 1. This gives us

$\begin{aligned} 217 &= 32 \cdot 6 + 25 \\ 32 &= 25 \cdot 1 + 7 \\ 25 &= 7 \cdot 3 + 4 \\ 7 &= 4 \cdot 1 + 3 \\ 4 &= 3 \cdot 1 + 1. \end{aligned}$

Next, express each remainder as a difference of the divident and a multiple of the divisor. That is, for each equation, subtract the product of the divisor and the quotient from both sides, and flip the equation:

$\begin{aligned} 25 &= 217 - 32 \cdot 6 \\ 7 &= 32 - 25 \\ 4 &= 25 - 7 \cdot 3 \\ 3 &= 7 - 4 \\ 1 &= 4 - 3. \end{aligned}$

Work backwards to express 1 as a sum of a multiple of the integer (217) and a multiple of the modulus (32):

$\begin{aligned} 1 &= 4 - 3 \\ &= 4 - (7 - 4) \\ &= 4 - 7 + 4 \\ &= 2 \cdot 4 - 7 \\ &= 2 (25 - 7 \cdot 3) - 7 \\ &= 2 \cdot 25 - 2 \cdot 7 \cdot 3 - 7 \\ &= 2 \cdot 25 - 7 \cdot 7 \\ &= 2 \cdot 25 - 7 (32 - 25) \\ &= 2 \cdot 25 - 7 \cdot 32 + 7 \cdot 25 \\ &= 9 \cdot 25 - 7 \cdot 32 \\ &= 9(217 - 32 \cdot 6) - 7 \cdot 32 \\ &= 9 \cdot 217 - 9 \cdot 32 \cdot 6 - 7 \cdot 32 \\ &= 217 \cdot 9 + 32 \cdot (-61). \end{aligned}$

Transform the last equation to have a multiple of the integer (217) on one side, and a sum of 1 and a multiple of the modulus (32) on the other side. The resulting equation is

$217 \cdot 9 = 1 + 32 \cdot 61$,

which implies

$217 \cdot 9 \equiv 1 \ (\textrm{mod} \ 32)$.

Thus, a modular multiplicative inverse of 217 under modulo 32 is 9.

Of course, any number of the form $9 + 32k$, with $k \in \mathbb{Z}$, is a modular multiplicative inverse of 217 under modulo 32. Generally, the smallest positive modular multiplicative inverse is used. If your result is negative, add the modulus to it as many times as needed to obtain a positive number. If your result is greater than the modulus, subtract the modulus from it until the result is smaller than the modulus.