Modular Inverses
In ordinary arithmetic, dividing by a means multiplying by
1/a. Modulo n there are no fractions — but
there can still be a number that acts like 1/a. It is called
the modular inverse of a, and finding it is how we
"divide" in clock arithmetic.
Definition
The inverse of a modulo n is a number
a^{-1} with
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.
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 huge moduli. If
\gcd(a, n) > 1, no inverse exists: that shared factor can never be
"undone".
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.