Modular Inverses and the Chinese Remainder Theorem

A modular inverse is simply the number that undoes multiplication on a clock: the inverse of $a$ is whatever you multiply $a$ by to get back to 1. It's called an "inverse" for the same reason $\frac13$ is the inverse of 3 in ordinary arithmetic, except mod $n$ there are no fractions, so the inverse has to be a whole number. It's how you "divide" in modular arithmetic, and it's the secret ingredient of RSA in the next lesson. The formula $a\,a^{-1} \equiv 1 \pmod{n}$ just says $a$ (your number) times $a^{-1}$ (its inverse) lands on 1, and the condition $\gcd(a, n) = 1$ (a and n share no common factor) tells you when that's possible. That's the whole lesson in one line.

In the last lesson you saw that you can add and multiply mod $n$ freely, but division was missing. In ordinary arithmetic, dividing by 3 is the same as multiplying by $\frac13$, the number that turns 3 into 1. So the question is whether mod $n$ there's a whole number that turns $a$ into 1.

Finding an inverse. For small $n$, just search: $3 \cdot 5 = 15 \equiv 1 \pmod 7$, so $3^{-1} \equiv 5$. For big $n$, Euclid's algorithm from two lessons ago does the work. If $\gcd(a, n) = 1$, Bézout gives $sa + tn = 1$. Now look at that mod $n$: the $tn$ term is a multiple of $n$, so it disappears, leaving $sa \equiv 1 \pmod n$. So $s$ is the inverse, and the extended Euclidean algorithm hands it to you.

What if $\gcd(a, n) = d > 1$? Then $ab$ and $n$ are both multiples of $d$, so $ab$ reduced mod $n$ is still a multiple of $d$, and it can never be $\equiv 1$. So 6 has no inverse mod 9: every multiple of 6 lands on 0, 3 or 6.

Solving $ax \equiv b \pmod n$. With an inverse in hand, this works just like solving $3x = 4$: multiply both sides by $a^{-1}$ to get $x \equiv a^{-1}b$. For $3x \equiv 4 \pmod 7$: $x \equiv 5 \cdot 4 = 20 \equiv 6$.

Chinese remainder theorem. It's named for the Chinese mathematician Sunzi, who posed a puzzle of this kind about 1,700 years ago (you'll meet it in the practice). If $m$ and $n$ are coprime, the system $x \equiv a \pmod m$, $x \equiv b \pmod n$ has exactly one solution mod $mn$. Here's a way to see why. There are $mn$ numbers from 0 to $mn - 1$, and $mn$ possible pairs of remainders. Two numbers in that range with the same pair would differ by a multiple of both $m$ and $n$, so a multiple of $mn$ (since they share no factor), and that's impossible unless they're equal. So every pair of remainders shows up exactly once. For $x \equiv 2 \pmod 3$ and $x \equiv 3 \pmod 5$, listing $3, 8, 13, \dots$ (the numbers $\equiv 3 \bmod 5$) finds $8 \equiv 2 \pmod 3$: so $x \equiv 8 \pmod{15}$.

RSA's private key is a modular inverse, and implementations use the Chinese remainder theorem to decrypt about four times faster.