The Chinese remainder theorem explained
A number leaves 2 when divided by 3, 3 when divided by 5 and 2 when divided by 7. Which number is it? Try the numbers one by one and you reach 23 after a while, but the question hides a theorem: as long as the divisors have no common factor, there is always exactly one answer below their product, and it can be found without trying anything. The theorem is about 1,500 years old and is still at work in calendars, computer arithmetic and the cryptography that protects the web.
A problem from the Sunzi Suanjing
The Sunzi Suanjing, a Chinese arithmetic book from the 3rd to 5th century, asks for a number of things that leaves 2 when counted by threes, 3 when counted by fives and 2 when counted by sevens. Its answer is 23, and its method is the one still taught: take 70 for each thing left over by threes, 21 for each left by fives and 15 for each left by sevens, add, and subtract 105 as often as you can. 2 × 70 + 3 × 21 + 2 × 15 = 233, and 233 − 2 × 105 = 23. A Ming-dynasty verse kept the numbers 70, 21, 15 and 105 in memory for centuries. Qin Jiushao gave a general method in 1247, the same problem appears in Fibonacci's Liber Abaci of 1202, and Carl Friedrich Gauss stated the theorem in its modern form in his Disquisitiones Arithmeticae of 1801.
What the theorem says
Take moduli n₁, n₂, …, nₖ of which no two have a common factor, and any remainders a₁, a₂, …, aₖ. Then there is exactly one whole number x from 0 to N − 1, where N = n₁ × n₂ × … × nₖ, that leaves the remainder aᵢ when divided by nᵢ, for every i. All other solutions differ from it by a multiple of N. In the notation of modular arithmetic: the system x ≡ aᵢ (mod nᵢ) has a solution, and it is unique mod N. Another way to say it is that a number from 0 to N − 1 and its list of remainders carry exactly the same information: 3 × 5 × 7 = 105 numbers, and 3 × 5 × 7 = 105 possible lists of remainders, each used once.
Building the solution
The numbers 70, 21 and 15 are not magic. Each one leaves 1 when divided by its own modulus and 0 when divided by the others: 70 = 2 × 35 is a multiple of 5 and 7 and leaves 1 when divided by 3. In general, take Nᵢ = N / nᵢ, which is a multiple of every modulus but nᵢ, and multiply it by yᵢ, the inverse of Nᵢ mod nᵢ. The inverse exists because Nᵢ and nᵢ have no common factor, and the extended Euclidean algorithm finds it: it runs Euclid's divisions for the greatest common divisor and works back to Bézout's identity 1 = s × nᵢ + t × Nᵢ, so that t is the inverse. Then x = a₁N₁y₁ + a₂N₂y₂ + … reduced mod N fits every equation, because each term fits its own equation and disappears in all the others.
One equation at a time
There is a second way, which needs no product of all the moduli. Every solution of x ≡ 2 (mod 3) has the form x = 2 + 3t. Put that into the next equation: 2 + 3t ≡ 3 (mod 5), so 3t ≡ 1 (mod 5), and multiplying by 2, the inverse of 3 mod 5, gives t ≡ 2 (mod 5). Then x = 2 + 3 × 2 = 8, and the first two equations together say x ≡ 8 (mod 15). Repeat with the third equation: 8 + 15t ≡ 2 (mod 7) gives t ≡ 1, so x ≡ 23 (mod 105). This substitution keeps the numbers smaller, is how a computer usually solves such systems, and still works when the moduli share a factor.
Moduli with a common factor
If two moduli share a factor, their equations overlap: x ≡ 1 (mod 4) already says that x is odd, and x ≡ 4 (mod 6) says that x is even, so no x satisfies both. In general x ≡ a (mod m) and x ≡ b (mod n) can both hold exactly when a and b leave the same remainder when divided by g = gcd(m, n), that is, when g divides a − b. Then the solution is unique mod lcm(m, n) = m × n / g, not mod m × n. The old puzzle of the basket of eggs, which leave 1 when taken out 2, 3, 4, 5 or 6 at a time and none when taken out 7 at a time, has the answer 301, repeating every 420 = lcm(2, 3, 4, 5, 6, 7). A system has a solution exactly when every two of its equations agree, so an impossible system always contains a pair that clashes.
Calendars, computers and RSA
In 1583 Joseph Scaliger combined three calendar cycles, the 28-year solar cycle, the 19-year lunar cycle and the 15-year indiction, into the Julian Period of 28 × 19 × 15 = 7,980 years. By the theorem every year has its own combination of the three cycle numbers, and the period begins in 4713 BC, the last year in which all three were 1; astronomers still count Julian days from it. Computers use the theorem to calculate with huge numbers as lists of small remainders, which can be added and multiplied separately and in parallel, then joined at the end. RSA decryption works the same way: c^d mod n with n = p × q is computed as two powers mod p and mod q and joined with the theorem, about four times faster than one power mod n. Secret-sharing schemes, such as those of Mignotte and of Asmuth and Bloom, hide a secret in remainders so that only enough of them together reveal it.
Explore it
Open the solver to type any system of congruences, with up to 20 equations and numbers of up to 200 digits, or pick one of the worked examples: Sunzi's problem, the basket of eggs, the Julian Period, two bus timetables, RSA decryption and a system with no solution. The working is written out with your numbers, by the construction or by substitution, with the extended Euclidean algorithm for every inverse. The picture marks the numbers that satisfy each equation, so you can see the one column where they all meet, or lays out the remainders of two equations in a table where every number has its own cell.
Frequently asked questions
Is the solution of a system of congruences unique?
Only up to a multiple of the modulus. If x = 23 solves Sunzi's problem, so do 23 + 105 = 128, 233 and −82, because adding 105 changes none of the remainders. The theorem says there is exactly one solution from 0 to 104; with moduli that share factors, exactly one below their least common multiple.
Why must the moduli be coprime?
For the construction, because Nᵢ must have an inverse mod nᵢ, and that exists only when they have no common factor. For the theorem itself, because shared factors make some equations overlap: then a system either has no solution or has fewer different ones, and the solutions repeat every least common multiple instead of every product.
How do I find a modular inverse by hand?
With the extended Euclidean algorithm. For the inverse of 15 mod 7: 15 = 2 × 7 + 1, so 1 = 15 − 2 × 7, and 15 × 1 ≡ 1 (mod 7): the inverse is 1. For 35 mod 3: 35 = 11 × 3 + 2 and 3 = 1 × 2 + 1, so 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, and the inverse of 35 mod 3 is −1 ≡ 2. For small moduli you can also simply try 1, 2, 3, … until the product leaves 1.
What does the theorem have to do with clocks?
A remainder mod n is a position on a clock with n hours. Two clocks with 3 and 5 hours, started together and advanced one hour at a time, show every one of the 15 pairs of positions once before they are back at the start, because 3 and 5 have no common factor. Clocks with 4 and 6 hours return after 12 steps and show only 12 of the 24 pairs: positions with an odd and an even number never appear together.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Open the Chinese remainder theorem solver