On this page
A number leaves remainder 2 when divided by 3, remainder 3 when divided by 5 and remainder 2 when divided by 7. What is it? This puzzle comes from the Sunzi suanjing, a Chinese text written between the 3rd and 5th century CE (Wikipedia: Chinese remainder theorem), and the same kind of question still appears in olympiad and aptitude practice. Below you will solve it step by step, see why the famous shortcut works, and get a short practice set with answers.
What number leaves remainders 2, 3 and 2 when divided by 3, 5 and 7?
The answer is 23. Check it: 23 = 3 × 7 + 2, 23 = 5 × 4 + 3, and 23 = 7 × 3 + 2.
The puzzle comes from the Sunzi suanjing, which the MacTutor History of Mathematics biography of Sun Zi words as: "Suppose we have an unknown number of objects. When counted in threes, 2 are left over, when counted in fives, 3 are left over, and when counted in sevens, 2 are left over." The Wikipedia article on the Chinese remainder theorem dates the text to the 3rd to 5th century CE.
Adding 105, which 3, 5 and 7 all divide, gives more answers: 128, 233 and so on, or 105k + 23.
How do you solve it step by step?
Take one condition at a time.
Start with the largest divisor. Remainder 2 on division by 7 means the number is 7k + 2: that is 2, 9, 16, 23, 30, 37...
Apply the second condition (remainder 3 on division by 5). Test the list: 2, 9 and 16 leave 2, 4 and 1; 23 leaves 3. So 23, 58, 93... satisfy both (they repeat every 35).
Apply the third condition. 23 leaves remainder 2 on division by 3. Done.
Write the general answer: 105k + 23.
In algebra, step 2 is 7k + 2 ≡ 3 (mod 5), which gives k ≡ 3 (mod 5), so the number is 35m + 23. Step 3 then forces m to be a multiple of 3.
Why does Sunzi's 70, 21, 15 trick work?
MacTutor quotes Sunzi's rule: multiply the remainder for 3 by 70, the remainder for 5 by 21 and the remainder for 7 by 15, add them, and subtract multiples of 105 (MacTutor). Here that is 2 × 70 + 3 × 21 + 2 × 15 = 140 + 63 + 30 = 233, and 233 − 210 = 23.
The magic numbers are chosen so that each one handles exactly one divisor:
70 is divisible by 5 and 7 and leaves remainder 1 on division by 3.
21 is divisible by 3 and 7 and leaves remainder 1 on division by 5.
15 is divisible by 3 and 5 and leaves remainder 1 on division by 7.
So 2 × 70 sets the remainder for 3 without disturbing 5 or 7. For other coprime divisors, take the product of the other divisors (35 for the divisor 3) and multiply until it leaves remainder 1 (35 × 2 = 70).
When does the Chinese remainder theorem guarantee an answer?
The Chinese remainder theorem says that if the divisors are pairwise coprime (no two share a factor), there is exactly one solution between 0 and their product (Wikipedia: Chinese remainder theorem). The same article records that Aryabhata described an algorithm for such problems in the 6th century, that Qin Jiushao gave a complete method in his 1247 Mathematical Treatise in Nine Sections, and that the theorem appears in Gauss's 1801 Disquisitiones Arithmeticae.
The coprime condition matters. Ask for remainder 1 on division by 4 and remainder 2 on division by 6 and there is no answer: the first makes the number odd, the second makes it even.
For the same skill from other angles, see finding remainders of large powers for JEE and the largest number that divides leaving given remainders.
Which shortcuts save time in exams?
Two patterns turn up again and again, and both reduce to an LCM, as in the bells-ringing LCM word problems.
Same remainder every time. Remainder 1 on division by 2, 3, 4, 5 and 6: the answer is LCM + 1 = 61, or 60k + 1.
Same gap every time. Remainders 2, 3 and 4 on division by 3, 4 and 5: each remainder is one less than its divisor, so the answer is LCM − 1 = 59.
Practice set:
Remainders 1, 2, 3 on division by 2, 3, 5. (Answer: 23, then every 30.)
Remainder 1 on division by 2, 3, 4, 5, 6 and divisible by 7. (Answer: 301.)
Remainders 3, 4, 1 on division by 4, 5, 7. (Answer: 99, then every 140.)
Got a different answer? The Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer, so you can find the step where your method slipped.
