Chinese remainder theorem
- Olympiad · IOQM
The Chinese remainder theorem says that if no two of the divisors share a factor other than 1, a number's remainders on them fix the number up to their product.
Say a number leaves remainder 2 when divided by 3, and remainder 3 when divided by 5. Since 3 and 5 are co-prime, there is exactly one such number from 0 to 14. Every other answer differs from it by a multiple of 15.
In the language of congruence, we solve x ≡ 2 (mod 3) and x ≡ 3 (mod 5) together. The theorem is named after a puzzle in an old Chinese text.
A small example
Find the smallest positive x with x ≡ 2 (mod 3) and x ≡ 3 (mod 5). List the numbers that fit the second rule first:
- 3 leaves 0 when divided by 3. No.
- 8 leaves 2 when divided by 3. Yes.
So x = 8. The next answers are 8 + 15 = 23, then 38, and so on. Check 23: it is 3 × 7 + 2 and 5 × 4 + 3.
The co-prime condition matters. Try x ≡ 1 (mod 2) and x ≡ 2 (mod 4). The first says x is odd. The second says x is even. No number does both, because 2 and 4 are not co-prime. With three or more divisors, every pair must be co-prime.
Where it fits
This goes beyond the Class 10 board syllabus. HBCSE's syllabus for the Mathematical Olympiad names it under number theory. The Mathematics Teachers' Association (India), MTA(I), conducts IOQM, the first stage of the Mathematical Olympiad Programme that HBCSE organises for NBHM.
Sources
Facts last checked against these sources on 30 September 2026.
- Syllabus for Mathematical Olympiad (Number Theory) · HBCSE, TIFR
- Mathematical Olympiad 2026-2027: stages of selection · HBCSE, TIFR
- Brochure: Mathematical Olympiads 2026-2027 · HBCSE, TIFR
About the author
Chief Architect
An engineer (B.Tech, Computer Science) with over 20 years of preparing students for entrance exams, including as Dean at FIITJEE and Vice-President at Aakash. He is the chief architect of the TRUpreBoards evaluation engine.
Mohit Sardana on LinkedIn