The Chinese remainder theorem looks like a puzzle about leftovers, and in school it is one. In an olympiad it does a different job. It lets you ask for a number that behaves in several unrelated ways at once, and it promises the number exists. Most of the problems that use it are existence problems.
The statement
Let and be coprime. Then for any residues and the system
has a solution, and the solution is unique modulo . For several moduli that are pairwise coprime, the same holds with the product of all of them. In words: knowing a number modulo and modulo is the same as knowing it modulo , and every pair of residues occurs exactly once.
You can check the last sentence on a small case. For and , the fifteen numbers give fifteen different pairs (remainder mod , remainder mod ), and there are exactly possible pairs. Nothing is repeated and nothing is missing.
Solving a system by hand
Find with , and .
Work one step at a time. The first condition gives . Put that in the second: , so , so , since . Then and . Put that in the third: , which is , so . Then , and the full answer is .
Check: , and . All three hold.
Why it is true
Take , so the first condition holds for every integer . The second condition says . Since and are coprime, has an inverse modulo , and there is exactly one modulo that works. That gives one in each block of consecutive integers. This is the whole proof, and it uses coprimality exactly once, to invert . You can write it in an exam in four lines.
The same fact is what makes Euler's totient multiplicative. Here is the number of integers from to that are coprime to . If and are coprime, a number is coprime to exactly when it is coprime to both, and by the theorem the residues pair up one to one. So .
The first use: build a number with prescribed properties
Is there a run of consecutive integers where each one is divisible by a perfect square larger than ? Yes, as long as you like. Here is a short run, so you can see the mechanism: find with , and .
The moduli are pairwise coprime, so the system , , has a solution modulo . The smallest is . Then , and . Three consecutive numbers, none of them squarefree.
To get a run of any length, use the first primes squared as the moduli. The classic problem asking for consecutive composite numbers can be done the same way, even though the archive solves it another way: choose distinct primes and ask that . The theorem hands you , and a little care that each is larger than makes them composite.
The second use: counting solutions
Count the solutions of .
Since , a number is a solution exactly when it is a solution modulo each prime. Modulo an odd prime the equation has exactly two solutions, , because forces or . The theorem says each choice of residues modulo , and gives one number modulo . So the count is . Writing them out: .
Any equation modulo a composite number splits this way: split the modulus into prime powers, count the solutions for each, and multiply. Modulo the same equation has solutions, and modulo it has . Take care with repeated primes. Modulo the equation has solutions, , so each prime power needs its own count. The modulus is the easy case because no prime repeats.
When to reach for it
- "Prove there exists a number such that ..." where the conditions are divisibility by different pairwise coprime numbers.
- A problem with arbitrarily long runs. Long runs of consecutive numbers with a shared property, arithmetic progressions of a given length with some property at each term.
- Counting residues modulo a composite. Split the modulus into prime powers, count each, multiply.
- Making a statement true at many primes at once. If has a root modulo each prime and you need for all of them at once, choose a root for each prime, then glue.
When the moduli share a factor
The theorem fails if you drop coprimality. The system and has no solution: the first forces odd and the second forces even.
The honest rule for moduli and with : a solution exists exactly when , and then it is unique modulo . For example and give .
The practical habit is to split non-coprime moduli into prime powers first. For each prime you keep the largest power, and you check that the smaller-power conditions agree with it. Then you glue the compatible ones.
What to write
State that the moduli are pairwise coprime. Name the theorem. Say which residues you are asking for. Then use the solution it gives you, noting that you only need it to exist and do not need its value. Many problems stop there, because existence is all they ask for. This is modular thinking in its plainest form: control the number one modulus at a time. Pick a run of five consecutive numbers with a property of your choice and build it. The problem archive has the classic version, and the daily problem is there when you want another.
Related guides
- Legendre's formula for the power of a prime in n!Legendre's formula gives the exponent of a prime in n! as a sum of floors. The proof, the digit-sum form, trailing zeros, and the traps that cost marks.
- Order modulo p in olympiad number theoryThe order of a modulo p divides p - 1 and every n with a^n = 1 mod p. How to use it to pin down prime factors, with a worked proof and the traps.
- Zsigmondy's theorem: statement, exceptions and examplesZsigmondy's theorem says a^n - b^n has a prime factor no earlier a^k - b^k has, with two exceptions. The statement, the traps, and a worked problem.
- EGMO 2020 Problem 1: solution, and the power of 2 that cannot hideA full solution to EGMO 2020 Problem 1: track the power of 2 in each term, show it climbs by 2 or falls by 1, and count the terms.
- EGMO 2025 Problem 1: solution, and the one pair that breaks the restA full solution to EGMO 2025 Problem 1: why every even N and every power of 3 works, the pair that breaks every other N, and the signal in the statement.
Techniques in this guide
- Modular ThinkingWhen the numbers are too big, shrink the universe.
Competitions this guide helps with
- Pascal, Cayley and Fermat25 questions: multiple choice in Parts A and B, and a whole number from 0 to 99 in Part C · 60 minutes
- UKMT Intermediate Challenge25 multiple-choice questions · 60 minutes
- SMO JuniorRound 1: multiple-choice and short-answer questions of equal weight. Round 2: full written solutions · 2.5 hours for Round 1, 3 hours for Round 2
Train it on Lemma
Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.
Find your level