Modular Inverses
In ordinary arithmetic, "divide by a" always means the same thing:
multiply by 1/a. That trick is how you undo a multiplication — if
3x = 12, multiplying both sides by 1/3 hands
you x = 4 immediately.
Modulo n there is no such thing as 1/a —
fractions don't exist in clock arithmetic. Try to "undo" the multiplication in
2x \equiv 2 \pmod 6 and it goes wrong fast: both
x \equiv 1 and x \equiv 4 work
(2 \cdot 4 = 8 \equiv 2), so you can't just "cancel the 2" the way you
would with real numbers. Something has broken.
The fix is a number that behaves like 1/a even though it isn't
a fraction: the modular inverse. It is the key that unlocks solving equations
modulo n — without it, "dividing" mod n is
simply not defined.
Definition
The inverse of a modulo n, written
a^{-1}, is a whole number that multiplies with
a to give 1, modulo n:
a \cdot a^{-1} \equiv 1 \pmod{n}.
For example, modulo 7 the inverse of 3 is
5, since 3 \cdot 5 = 15 \equiv 1 \pmod 7. To
"divide by 3" mod 7, you multiply by
5 instead — and it always gives the right answer, because that's exactly
what an inverse is for.
Note the phrase "modulo n" is doing real work here:
3's inverse mod 7 is 5,
but its inverse mod 11 is a completely different number
(4, since 3 \cdot 4 = 12 \equiv 1 \pmod{11}). The
inverse always depends on which modulus you're working in.
When does an inverse exist?
a has an inverse modulo n if and
only if \gcd(a, n) = 1 — that is, when
a and n are coprime.
The reason is pure Bézout.
If \gcd(a, n) = 1 then there are integers
x, y with
ax + ny = 1 \;\Longrightarrow\; ax \equiv 1 \pmod n,
so x is the inverse. And the
extended Euclidean algorithm
computes that x directly — fast, even for moduli hundreds of digits long.
If \gcd(a, n) > 1, no inverse exists at all: that shared factor can never
be "undone" by multiplying.
Worked example: finding an inverse by trial
For a small modulus, the most honest way to see an inverse is to just try every candidate.
What is 3^{-1} \pmod 7? Check \gcd(3, 7) = 1
first, so an inverse is guaranteed to exist. Then multiply 3 by
1, 2, 3, \dots and reduce each product mod 7:
3 \cdot 1 = 3,\quad 3 \cdot 2 = 6,\quad 3 \cdot 3 = 9 \equiv 2,\quad 3 \cdot 4 = 12 \equiv 5,\quad
3 \cdot 5 = 15 \equiv 1.
There it is — 3 \cdot 5 \equiv 1 \pmod 7, so
3^{-1} \equiv 5 \pmod 7. As a sanity check, notice the remainders
3, 6, 2, 5, 1 visited five different nonzero residues before
landing on 1 — with a prime modulus that always happens eventually,
because every nonzero residue is coprime to a prime.
Trial-and-error is fine for a modulus like 7, but it is hopeless for the
moduli actually used in practice — hundreds of digits long. For those you need a method that
computes the inverse instead of guessing it, which is exactly what
Euclid's ancient algorithm, souped up, gives us.
Worked example: finding an inverse with the extended Euclidean algorithm
Find 5^{-1} \pmod{11}. First confirm
\gcd(5, 11) = 1 by running the Euclidean algorithm, keeping every
remainder step so it can be reversed:
11 = 2 \cdot 5 + 1, \qquad 5 = 5 \cdot 1 + 0.
The last nonzero remainder is 1, confirming
\gcd(5, 11) = 1 — good, an inverse exists. Now walk the division back
upward to write that 1 as a combination of 5
and 11. The first line already says it, rearranged:
1 = 11 - 2 \cdot 5.
Read this modulo 11: the 11 term vanishes
(it's \equiv 0), leaving
-2 \cdot 5 \equiv 1 \pmod{11}.
So -2 is an inverse of 5 — but by convention
we report inverses as a residue between 0 and
n - 1, so add 11:
-2 \equiv 9 \pmod{11}. Check it:
5 \cdot 9 = 45 = 44 + 1 \equiv 1 \pmod{11}. It works, so
5^{-1} \equiv 9 \pmod{11}. This "back-substitution" is exactly what the
extended Euclidean algorithm automates, step by step, no matter how large the numbers get.
A shortcut when the modulus is prime
There is a second way to find an inverse modulo a prime p, and
it needs no back-substitution at all. Fermat's Little Theorem says that for any
a not a multiple of p,
a^{p-1} \equiv 1 \pmod p.
Peel one power of a off the left-hand side and this reads
a \cdot a^{p-2} \equiv 1 \pmod p — which is precisely the definition of
an inverse. So a^{p-2}, reduced mod p, is
the inverse of a. Check it against the earlier example: modulo the prime
11, 5^{-1} should equal
5^{11-2} = 5^9 \bmod 11. Working it out step by step,
5^2 \equiv 3, 5^4 \equiv 9,
5^8 \equiv 81 \equiv 4, so
5^9 \equiv 4 \cdot 5 = 20 \equiv 9 \pmod{11} — the same
9 found the other way. This is a handy check by hand, and it is exactly
how a computer can find an inverse using nothing but repeated squaring when the modulus is prime.
Computing an inverse in code
Real software never searches by trial — it runs the extended Euclidean algorithm, keeping track of
two running combinations of a and n as it
goes, until the remainder hits zero. Run this to compute the same inverse of
5 mod 11 found by hand above:
function modInverse(a: number, n: number): number | null {
let [oldR, r] = [a, n];
let [oldS, s] = [1, 0];
while (r !== 0) {
const quotient = Math.floor(oldR / r);
[oldR, r] = [r, oldR - quotient * r];
[oldS, s] = [s, oldS - quotient * s];
}
if (oldR !== 1) return null; // gcd(a, n) !== 1 — no inverse exists
return ((oldS % n) + n) % n; // normalise into [0, n)
}
console.log(modInverse(5, 11)); // 9
console.log(modInverse(3, 7)); // 5
console.log(modInverse(4, 8)); // null — gcd(4, 8) = 4
Notice the function returns \texttt{null} instead of a number whenever
\gcd(a, n) \ne 1 — the code has to handle "no inverse exists" as a real
possibility, not an error to hide.
It is tempting to think that finding an inverse is just sometimes hard — a bigger number to
crunch, a longer search. It isn't. When \gcd(a, n) \ne 1, an inverse does
not exist, full stop, no matter how cleverly or how long you search.
Take 4^{-1} \pmod 8. Every multiple of 4,
reduced mod 8, is one of exactly two values:
4 \cdot 1 \equiv 4, \quad 4 \cdot 2 \equiv 0, \quad 4 \cdot 3 \equiv 4, \quad 4 \cdot 4 \equiv 0, \; \dots
The pattern just alternates between 4 and 0
forever — 1 is never among them. The shared factor
\gcd(4, 8) = 4 guarantees every multiple of 4
mod 8 stays a multiple of that same 4, and
1 is not one. So before hunting for an inverse, always check
\gcd(a, n) = 1 first — it tells you in one line whether the search can
possibly succeed.
Why this fixes division
Recall the failed cancellation 2 \cdot 3 \equiv 2 \cdot 0 \pmod 6. The
culprit: \gcd(2, 6) = 2 \ne 1, so 2 has no
inverse mod 6 and cannot be cancelled. But modulo a
prime p, every nonzero element is coprime to
p, so every nonzero element is invertible — and cancellation always
works. That is what makes \mathbb{Z}_p a
field, and
it is the secret reason primes are so central to the subject.
Modular inverses are not just a classroom curiosity — they sit inside one of the most-used pieces of
mathematics on the planet. The RSA encryption scheme, which protects a huge share of
secure web traffic, works by choosing a public number e and a modulus
n, then computing the decryption key as the modular inverse of
e — not modulo n itself, but modulo a related
number built from n's prime factors.
That single inverse — found with the extended Euclidean algorithm, on numbers hundreds of digits
long — is the whole reason the padlock icon in your browser's address bar can lock a message up so
that only the intended recipient can undo it. Every time you load a page over
\texttt{https://}, a modular inverse gets computed somewhere behind the
scenes to make it possible.