Image: Qing dynasty print of the Sunzi Suanjing, Wikimedia Commons (public domain)Sunzi's puzzle and the Chinese remainder theorem
"There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; by sevens, two are left over. How many things are there?" The question is from the Sunzi Suanjing, the Mathematical Classic of Master Sun, a Chinese text written some time between the third and fifth centuries AD. The answer given is 23, and the method given with it is the Chinese remainder theorem in everything but name.
Solving it by hand
The slow way is to list the numbers that leave remainder 2 on division by 3, namely 2, 5, 8, 11, 14, 17, 20, 23, ..., strike out those that do not leave remainder 3 on division by 5, which leaves 8, 23, 38, ..., and then keep those that leave remainder 2 on division by 7. The first survivor is 23, and the next is 23 + 105 = 128, since 105 = 3 × 5 × 7 is the first point at which all three cycles realign.
Sunzi's method is faster and generalizes. Find a number that is a multiple of 5 and 7 and leaves remainder 1 on division by 3: that is 70. Find one that is a multiple of 3 and 7 with remainder 1 on division by 5: that is 21. Find one that is a multiple of 3 and 5 with remainder 1 on division by 7: that is 15. Then the answer is 2 × 70 + 3 × 21 + 2 × 15 = 140 + 63 + 30 = 233, and since any multiple of 105 can be added or removed, 233 - 210 = 23. The text states the three helper numbers 70, 21, and 15 and the rule "subtract 105 until the number is small", which is the whole algorithm.
Why does it work? Look at 70 modulo each of the three divisors: it is 1 modulo 3, and 0 modulo 5 and modulo 7. So 2 × 70 contributes exactly 2 to the remainder on division by 3 and nothing to the other two. Each term of the sum handles one condition and stays invisible to the others. That is the entire idea.
The theorem
In modern language: if n₁, n₂, ..., n_k are pairwise coprime positive integers and a₁, ..., a_k are any integers, then the system of congruences x ≡ a₁ (mod n₁), ..., x ≡ a_k (mod n_k) has a solution, and the solution is unique modulo the product N = n₁ n₂ ... n_k.
The proof is Sunzi's construction. Let N_i = N / n_i, the product of all the moduli except n_i. Since the moduli are pairwise coprime, N_i and n_i have no common factor, so by Bézout's identity there is an integer M_i with N_i M_i ≡ 1 (mod n_i); it is found with the extended Euclidean algorithm. Then x = a₁ N₁ M₁ + ... + a_k N_k M_k satisfies every congruence, because the i-th term is a_i modulo n_i and every other term is a multiple of n_i. Uniqueness: if x and y are two solutions, their difference is divisible by every n_i, hence by their product, since they are pairwise coprime. For Sunzi's problem, N₁ = 35, M₁ = 2, and 35 × 2 = 70; N₂ = 21, M₂ = 1; N₃ = 15, M₃ = 1. The helper numbers are exactly the ones in the text.
The coprimality condition is essential. The system x ≡ 1 (mod 2), x ≡ 0 (mod 4) has no solution, and x ≡ 1 (mod 2), x ≡ 3 (mod 4) has solutions but they are unique only modulo 4, not modulo 8. Unit 4 of the masterclass treats the general case, in which the system is solvable exactly when each pair of congruences agrees modulo the gcd of their moduli.
From puzzle to structure
The theorem has a second reading that is more important than the first. It says that knowing a number modulo 105 is the same as knowing it modulo 3, modulo 5, and modulo 7 at once. The residues modulo 105 and the triples of residues modulo 3, 5, and 7 are in one-to-one correspondence, and the correspondence respects addition and multiplication. Arithmetic modulo 105 is three independent small arithmetics running in parallel.
That is why so many formulas in number theory are "multiplicative", meaning they can be computed one prime power at a time. Euler's function φ(n), which counts the residues modulo n that have an inverse, satisfies φ(105) = φ(3) φ(5) φ(7) = 2 × 4 × 6 = 48 for exactly this reason: an invertible residue modulo 105 is a triple of invertible residues. The number of solutions of x² ≡ 1 (mod 105) is 2 × 2 × 2 = 8, because each prime contributes two square roots of 1 and the theorem lets you combine them freely. Unit 5 of the masterclass proves the product formula for φ this way, and Unit 9 uses the same decomposition to describe which moduli have primitive roots.
Where it is used today
The theorem appears wherever large numbers are handled in pieces.
Computer algebra systems multiply enormous integers and polynomials by reducing them modulo several primes that fit in a machine word, doing the arithmetic in parallel, and reassembling the answer with the Chinese remainder theorem. The reassembly is cheap and the parallel pieces are fast, so this is how a system such as PARI/GP or Sage computes a determinant with hundred-digit entries.
RSA decryption, which raises a number to a large power modulo n = pq, is routinely done modulo p and modulo q separately and then combined. The exponents can be reduced using Fermat's little theorem in each piece, and the two computations are about four times faster together than the single computation modulo n. Almost every RSA implementation does this, and it is also the source of a famous attack: if a hardware fault corrupts one of the two half-computations, the faulty signature combined with a correct one reveals the factor p by a single gcd. The RSA article on this blog gives the full computation with p = 61 and q = 53.
Secret sharing schemes split a secret into pieces so that any k of them reconstruct it and fewer than k reveal nothing; one of the classical constructions, due to Asmuth and Bloom, uses residues modulo a sequence of coprime moduli and the theorem to reassemble. Error-correcting codes for transmission, hashing of large keys, and the scheduling of periodic events that must coincide all lean on the same fact that remainders modulo coprime moduli are independent.
Other versions of the same idea
Sunzi was not the only early author. Aryabhata, in India around AD 500, gave a method called kuttaka, "the pulverizer", for finding a number with given remainders, which is in effect the extended Euclidean algorithm run on the two moduli. Qin Jiushao, in the Mathematical Treatise in Nine Sections of 1247, gave the general method for many moduli with a procedure for the inverses, and used it on calendar problems: when do the cycles of the sun, the moon, and the sexagenary day count coincide? In Europe, the problem appears in Fibonacci's Liber Abaci of 1202, and Gauss gave the modern formulation in Article 36 of the Disquisitiones Arithmeticae of 1801, with the congruence notation he had just introduced. The name "Chinese remainder theorem" became standard in the twentieth century, when historians traced the method to Sunzi.
The puzzle was also a party trick. Ask someone to think of a number below 105, tell you its remainders on division by 3, 5, and 7, and announce the number: multiply the remainders by 70, 21, and 15, add, and reduce modulo 105. It is the same computation Sunzi wrote down sixteen centuries ago, and a Python console does it in one line: the list comprehension over the integers below 105 that checks the three remainders returns [23]. Unit 4 of the masterclass proves the theorem, solves systems of several congruences in several unknowns, and uses it for the check digits on books, barcodes, and bank accounts that most people handle every day without noticing.


