Lemma › Guides › Chinese remainder theorem in olympiad problems
Guide

Chinese remainder theorem in olympiad problems

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 mm and nn be coprime. Then for any residues aa and bb the system

x≡a(modm),x≡b(modn)x \equiv a \pmod m, \qquad x \equiv b \pmod n

has a solution, and the solution is unique modulo mnmn. For several moduli that are pairwise coprime, the same holds with the product of all of them. In words: knowing a number modulo mm and modulo nn is the same as knowing it modulo mnmn, and every pair of residues occurs exactly once.

You can check the last sentence on a small case. For m=3m = 3 and n=5n = 5, the fifteen numbers 0,1,…,140, 1, \dots, 14 give fifteen different pairs (remainder mod 33, remainder mod 55), and there are exactly 3⋅5=153 \cdot 5 = 15 possible pairs. Nothing is repeated and nothing is missing.

Solving a system by hand

Find xx with x≡2(mod3)x \equiv 2 \pmod 3, x≡3(mod5)x \equiv 3 \pmod 5 and x≡2(mod7)x \equiv 2 \pmod 7.

Work one step at a time. The first condition gives x=2+3tx = 2 + 3t. Put that in the second: 2+3t≡3(mod5)2 + 3t \equiv 3 \pmod 5, so 3t≡1(mod5)3t \equiv 1 \pmod 5, so t≡2(mod5)t \equiv 2 \pmod 5, since 3⋅2=63 \cdot 2 = 6. Then t=2+5st = 2 + 5s and x=8+15sx = 8 + 15s. Put that in the third: 8+15s≡2(mod7)8 + 15s \equiv 2 \pmod 7, which is 1+s≡21 + s \equiv 2, so s≡1(mod7)s \equiv 1 \pmod 7. Then x=8+15=23x = 8 + 15 = 23, and the full answer is x≡23(mod105)x \equiv 23 \pmod{105}.

Check: 23=7⋅3+223 = 7 \cdot 3 + 2, 23=4⋅5+323 = 4 \cdot 5 + 3 and 23=3⋅7+223 = 3 \cdot 7 + 2. All three hold.

Why it is true

Take x=a+mtx = a + mt, so the first condition holds for every integer tt. The second condition says mt≡b−a(modn)mt \equiv b - a \pmod n. Since mm and nn are coprime, mm has an inverse modulo nn, and there is exactly one tt modulo nn that works. That gives one xx in each block of mnmn consecutive integers. This is the whole proof, and it uses coprimality exactly once, to invert mm. You can write it in an exam in four lines.

The same fact is what makes Euler's totient multiplicative. Here φ(n)\varphi(n) is the number of integers from 11 to nn that are coprime to nn. If mm and nn are coprime, a number is coprime to mnmn exactly when it is coprime to both, and by the theorem the residues pair up one to one. So φ(mn)=φ(m)φ(n)\varphi(mn) = \varphi(m)\varphi(n).

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 11? Yes, as long as you like. Here is a short run, so you can see the mechanism: find xx with 4∣x4 \mid x, 9∣x+19 \mid x + 1 and 25∣x+225 \mid x + 2.

The moduli 4,9,254, 9, 25 are pairwise coprime, so the system x≡0(mod4)x \equiv 0 \pmod 4, x≡−1(mod9)x \equiv -1 \pmod 9, x≡−2(mod25)x \equiv -2 \pmod{25} has a solution modulo 900900. The smallest is x=548x = 548. Then 548=4⋅137548 = 4 \cdot 137, 549=9⋅61549 = 9 \cdot 61 and 550=25⋅22550 = 25 \cdot 22. Three consecutive numbers, none of them squarefree.

To get a run of any length, use the first kk primes squared as the moduli. The classic problem asking for nn consecutive composite numbers can be done the same way, even though the archive solves it another way: choose distinct primes p1,…,pnp_1, \dots, p_n and ask that pi∣x+ip_i \mid x + i. The theorem hands you xx, and a little care that each x+ix + i is larger than pip_i makes them composite.

The second use: counting solutions

Count the solutions of x2≡1(mod105)x^2 \equiv 1 \pmod{105}.

Since 105=3⋅5⋅7105 = 3 \cdot 5 \cdot 7, a number is a solution exactly when it is a solution modulo each prime. Modulo an odd prime pp the equation x2≡1x^2 \equiv 1 has exactly two solutions, x≡±1x \equiv \pm 1, because p∣(x−1)(x+1)p \mid (x-1)(x+1) forces p∣x−1p \mid x - 1 or p∣x+1p \mid x + 1. The theorem says each choice of residues modulo 33, 55 and 77 gives one number modulo 105105. So the count is 2⋅2⋅2=82 \cdot 2 \cdot 2 = 8. Writing them out: 1,29,34,41,64,71,76,1041, 29, 34, 41, 64, 71, 76, 104.

Any equation modulo a composite number splits this way: split the modulus into prime powers, count the solutions for each, and multiply. Modulo 1515 the same equation has 44 solutions, and modulo 33 it has 22. Take care with repeated primes. Modulo 88 the equation x2≡1x^2 \equiv 1 has 44 solutions, 1,3,5,71, 3, 5, 7, so each prime power needs its own count. The modulus 105105 is the easy case because no prime repeats.

When to reach for it

When the moduli share a factor

The theorem fails if you drop coprimality. The system x≡1(mod4)x \equiv 1 \pmod 4 and x≡2(mod6)x \equiv 2 \pmod 6 has no solution: the first forces xx odd and the second forces xx even.

The honest rule for moduli mm and nn with g=gcd⁡(m,n)g = \gcd(m, n): a solution exists exactly when a≡b(modg)a \equiv b \pmod g, and then it is unique modulo lcm⁡(m,n)\operatorname{lcm}(m, n). For example x≡2(mod4)x \equiv 2 \pmod 4 and x≡4(mod6)x \equiv 4 \pmod 6 give x≡10(mod12)x \equiv 10 \pmod{12}.

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

Techniques in this guide

Competitions this guide helps with

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