The Chinese remainder theorem
Tonight's idea
A problem from Sunzi's Mathematical Classic, written in China some sixteen centuries ago: find a number leaving remainder \(2\) when divided by \(3\), \(3\) when divided by \(5\), and \(2\) when divided by \(7\). In the notation of clock arithmetic, where \(a \equiv b \pmod m\) means \(m\) divides \(a - b\):
\[x \equiv 2 \pmod 3, \qquad x \equiv 3 \pmod 5, \qquad x \equiv 2 \pmod 7.\]
If the moduli are pairwise coprime (no two share a factor), there is exactly one solution modulo their product, here \(3 \cdot 5 \cdot 7 = 105\).
Why unique. If \(x\) and \(y\) both work, \(x - y\) is divisible by \(3\), by \(5\) and by \(7\). Coprime divisors multiply: \(105\) divides \(x - y\). So any two solutions agree mod \(105\).
Why one exists. Each residue \(0, \ldots, 104\) gives a triple of remainders \((x \bmod 3,\ x \bmod 5,\ x \bmod 7)\). By uniqueness, no two residues give the same triple. There are \(3 \cdot 5 \cdot 7 = 105\) possible triples. So \(105\) residues land on \(105\) triples without repeats: every triple, including \((2, 3, 2)\), is hit exactly once. The figure shows two moduli.
Coprimality matters: \(x \equiv 1 \pmod 4\), \(x \equiv 2 \pmod 6\) has no solution, since the first makes \(x\) odd and the second even.
Watch one: building the answer from switches
For each modulus, multiply the other two: \(35\), \(21\), \(15\). Now \(35\) is \(0\) mod \(5\) and mod \(7\); mod \(3\) it is \(2\), and \(2 \cdot 2 = 4 \equiv 1\), so \(e_1 = 2 \cdot 35 = 70\) has remainders \((1, 0, 0)\). Already \(21 \equiv 1 \pmod 5\) and \(15 \equiv 1 \pmod 7\), so \(e_2 = 21\) gives \((0, 1, 0)\) and \(e_3 = 15\) gives \((0, 0, 1)\). These are switches. Scale by the wanted remainders and add:
\[x = 2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 = 233 \equiv 23 \pmod{105}.\]
Check: \(23 = 7 \cdot 3 + 2 = 4 \cdot 5 + 3 = 3 \cdot 7 + 2\). Every solution is \(23 + 105k\).
RSA works mod \(pq\) (mathdetours.com/demos/rsa.html); computers use this theorem to work mod \(p\) and mod \(q\) separately, then recombine.
Your turn
- Find every \(x\) with \(x \equiv 1 \pmod 3\) and \(x \equiv 2 \pmod 4\).
- Solve \(x \equiv 1 \pmod 4\), \(x \equiv 2 \pmod 5\), \(x \equiv 3 \pmod 9\) by the switch method. Give the switches and the answer mod \(180\).
- \(4\) and \(6\) are not coprime. (a) Show that \(x \equiv 1 \pmod 4\), \(x \equiv 3 \pmod 6\) does have solutions, and find them all. (b) For which pairs of remainders \(a, b\) is \(x \equiv a \pmod 4\), \(x \equiv b \pmod 6\) solvable?
- A basket of eggs. Counted in twos, threes, fours, fives or sixes, one is always left over; counted in sevens, none. Smallest possible number of eggs? First collapse the five "one left over" conditions into one congruence.
Stretch: square roots of 1
Modulo an odd prime \(p\), \(x^2 \equiv 1\) has only the solutions \(\pm 1\), because \(p\) must divide \((x - 1)(x + 1)\). How many solutions does \(x^2 \equiv 1 \pmod{105}\) have? Count them with the theorem, then list them.
Answers
- Numbers that are \(2 \pmod 4\): \(2, 6, 10, \ldots\); the first that is \(1 \pmod 3\) is \(10\). So \(x \equiv 10 \pmod{12}\): \(10, 22, 34, \ldots\)
- \(M = 180\); \(M_1 = 45\), \(M_2 = 36\), \(M_3 = 20\). \(45 \equiv 1 \pmod 4\) so \(e_1 = 45\); \(36 \equiv 1 \pmod 5\) so \(e_2 = 36\); \(20 \equiv 2 \pmod 9\) and \(2 \cdot 5 = 10 \equiv 1\), so \(e_3 = 5 \cdot 20 = 100\). Then \(x = 1 \cdot 45 + 2 \cdot 36 + 3 \cdot 100 = 417 \equiv 57 \pmod{180}\). Check: \(57 = 14 \cdot 4 + 1 = 11 \cdot 5 + 2 = 6 \cdot 9 + 3\).
- (a) \(1 \pmod 4\): \(1, 5, 9, 13, 17, 21, \ldots\); of these, \(9\) and \(21\) are \(3 \pmod 6\). The solutions are \(x \equiv 9 \pmod{12}\): the modulus is the lowest common multiple \(12\), not the product \(24\). (b) Both conditions fix \(x \bmod 2\) (the shared factor \(\gcd(4, 6) = 2\)): \(x \equiv a \pmod 2\) and \(x \equiv b \pmod 2\). Solvable exactly when \(a\) and \(b\) have the same parity, and then there is one solution mod \(12\).
- One left over when counted in \(2, 3, 4, 5, 6\) means \(x - 1\) is divisible by all of them, so by \(\operatorname{lcm} = 60\): \(x \equiv 1 \pmod{60}\). Combine with \(x \equiv 0 \pmod 7\) (coprime to \(60\)). Try \(1, 61, 121, 181, 241, 301\): \(301 = 7 \cdot 43\). Smallest \(301\); in general \(x \equiv 301 \pmod{420}\).
Stretch. \(x^2 \equiv 1 \pmod{105}\) holds exactly when \(x^2 \equiv 1\) mod \(3\), mod \(5\) and mod \(7\) at once. Each gives two choices, \(x \equiv \pm 1\), and by the theorem every one of the \(2 \cdot 2 \cdot 2 = 8\) combinations is a different residue mod \(105\). The eight are \(1, 29, 34, 41, 64, 71, 76, 104\), in four \(\pm\) pairs (\(104 = -1\), \(76 = -29\), \(71 = -34\), \(64 = -41\)). For instance \(29 \equiv (-1, -1, 1)\) mod \((3, 5, 7)\), and \(29^2 = 841 = 8 \cdot 105 + 1\). An odd modulus with two or more different prime factors always has extra square roots of \(1\) like these, and finding one is a way to show a number is composite without factoring it.