On this page
"Find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7." Olympiad students meet this as the Chinese remainder theorem. Most learn it as a formula. The person who first turned a single puzzle into a general procedure was a 13th-century Chinese official with a remarkably bad reputation. This post covers who Qin Jiushao was, the puzzle he built on, how his method works, and the mistakes students make with remainders.
Where did the remainder problem start?
The puzzle above comes from the *Sunzi suanjing*, a Chinese manual whose date historians place anywhere from the 3rd to the 5th century. The MacTutor biography of Sun Zi calls it "the earliest known occurrence of this type of problem" and gives the answer, 23. The manual then gives a rule for any remainders: multiply the remainder on division by 3 by 70, the remainder for 5 by 21 and the remainder for 7 by 15, add, and subtract multiples of 105.
Who was Qin Jiushao?
The MacTutor biography of Qin Jiushao gives his dates as 1202 to 1261. He grew up in Sichuan, studied at the Board of Astronomy in the capital Hangzhou as a young man, and learned mathematics from what he called "a recluse scholar". He served as a soldier and then an official, and MacTutor records a career marked by corruption: dismissals, illegal dealings in salt and a contemporary who described him to the emperor as "as violent as a tiger, or a wolf".
During a period of mourning for his mother in 1244, he wrote the *Shushu Jiuzhang* (*Mathematical Treatise in Nine Sections*), which appeared in 1247. Its chapters cover the calendar, surveying, taxes and military affairs. It reduces some problems to polynomial equations, one of degree 10, solves cubics and quartics by the Chinese method now called Ruffini-Horner, and uses a small circle for zero. MacTutor notes that he did not claim the remainder method as his own: he said he learned it from calendar experts who used the rule without understanding it.
What did Qin add?
Sun Zi's rule only works when the divisors share no common factor. Qin's first chapter, MacTutor explains, deals with the general case. When the divisors are not pairwise coprime, he replaces them, in several passes, with coprime ones that give the same solution. He then solves each congruence separately and reassembles the answer. He even allowed divisors that were fractions, converting them to whole numbers first. MacTutor adds that Euler did not give a satisfactory solution to such problems and that the method was later rediscovered by Gauss and others. A detailed history is Shen Kangsheng's Historical development of the Chinese remainder theorem (1988).
Worked example 1: Sun Zi's puzzle the modern way
Find x with x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).
The product of the divisors is 3 × 5 × 7 = 105.
For mod 3: 105/3 = 35, and 35 leaves 2 on division by 3. Multiply by 2 to get 70, which leaves 1. So the multiplier is 70.
For mod 5: 105/5 = 21, which already leaves 1 on division by 5.
For mod 7: 105/7 = 15, which leaves 1 on division by 7.
x = 2 × 70 + 3 × 21 + 2 × 15 = 140 + 63 + 30 = 233.
Subtract 105 twice: 233 − 210 = 23. Check: 23 = 3 × 7 + 2 = 5 × 4 + 3 = 7 × 3 + 2.
Step 2 is the hard part in general: finding a multiplier that leaves remainder 1. For large numbers the Euclidean algorithm does it.
Worked example 2: divisors that share a factor
This is the kind of case Qin's method handles. Find x with x ≡ 1 (mod 4) and x ≡ 3 (mod 6). The divisors 4 and 6 share the factor 2, so Sun Zi's rule fails.
Split 6 = 2 × 3. The condition x ≡ 3 (mod 6) means x is odd and x is a multiple of 3.
"x is odd" is already implied by x ≡ 1 (mod 4), so drop it. The divisors are now 4 and 3, which are coprime.
Solve x ≡ 1 (mod 4) and x ≡ 0 (mod 3): try multiples of 3 until one leaves 1 on division by 4. 3, 6, 9: 9 = 2 × 4 + 1.
So x ≡ 9 (mod 12). Check: 9 = 4 × 2 + 1 and 9 = 6 × 1 + 3.
If the shared factor gives conflicting conditions, such as x ≡ 1 (mod 4) and x ≡ 2 (mod 6), there is no solution at all: the first makes x odd, the second even.
What mistakes do students make with remainder problems?
Using the coprime formula when divisors share factors. Always check the greatest common divisor first, as in example 2.
Forgetting to reduce. 233 is a correct solution, but the smallest positive one is 23. Every answer repeats every 105.
Skipping the check. Substituting back takes ten seconds and catches most arithmetic slips.
Remainder problems appear in olympiad number theory, covered in our post on IOQM number theory questions. When a step like finding the multiplier feels like a trick, the Fermi Concept Library covers every concept in physics, chemistry, biology, mathematics and computing, so you can go back to modular arithmetic itself.
What can a student take from Qin's way of working?
His character is a warning, not a model. His mathematics is the opposite. He took a rule that others used without understanding and asked when it works, when it fails and how to fix the failing case. That habit is worth copying: whenever you learn a formula, find the condition it needs and try an example that breaks it.
Try it now: find the smallest positive x with x ≡ 3 (mod 8) and x ≡ 5 (mod 12), or show that none exists.
