The Chinese Remainder Theorem in One Sentence

The Chinese Remainder Theorem (CRT) sounds ancient and elaborate. It is ancient — Sun Tzu wrote it down around the 3rd century CE — but the content fits into one sentence:

If the moduli are pairwise coprime, a system of congruences x \equiv a_i \pmod{n_i} has exactly one solution modulo the product n_1 n_2 \cdots n_k.

That is the whole theorem. The rest is consequences.

Unpacking the sentence

Each congruence x \equiv a_i \pmod{n_i} picks out a residue class — the set of integers that leave remainder a_i when divided by n_i. Individually, each class is infinite. Intersecting two classes cuts the count down; intersecting all of them cuts it down to a single class modulo the product.

Coprime moduli. "Pairwise coprime" means every pair of moduli has \gcd = 1. If two moduli share a prime factor, the theorem's guarantee breaks — the system might have no solution, or it might have a solution but one that only determines x modulo the lcm, not the product.

Exactly one solution mod n_1 n_2 \cdots n_k. This is what makes CRT so powerful: you get uniqueness at the level of the combined modulus. So if you have two coprime conditions like x \equiv 2 \pmod 3 and x \equiv 3 \pmod 5, there is a unique x modulo 15 that satisfies both.

The one-sentence example everyone should see

Solve:

x \equiv 2 \pmod 3, \qquad x \equiv 3 \pmod 5.

Both moduli are prime, so they are coprime. By CRT, a unique x modulo 15 satisfies both.

Finding it. List the class x \equiv 2 \pmod 3: \{\ldots, -1, 2, 5, 8, 11, 14, 17, \ldots\}. Now check which of these satisfy x \equiv 3 \pmod 5. Compute each mod 5:

2 \bmod 5 = 2. No.
5 \bmod 5 = 0. No.
8 \bmod 5 = 3. Yes.
11 \bmod 5 = 1. No.
14 \bmod 5 = 4. No.

x = 8 is a solution. By CRT, the full solution set is x \equiv 8 \pmod{15} — one residue class mod 15, consistent with the theorem's guarantee.

Two clocks — a mod-$3$ clock pointed at $2$ and a mod-$5$ clock pointed at $3$. The only time (mod $15$) that both clocks show together is $x = 8$. CRT says that because $\gcd(3, 5) = 1$, any pair of clock readings you name has exactly one common time in the combined cycle of length $15$.

Why "one sentence" is actually enough

The deceptive simplicity hides three separate claims bundled together.

Claim 1: A solution exists. For coprime moduli, you can always find some x satisfying all the congruences simultaneously.

Claim 2: The solution is unique modulo n_1 n_2 \cdots n_k. Two different solutions x and y would have x \equiv y \pmod{n_i} for every i, so every n_i divides x - y. Since the n_i are pairwise coprime, their product also divides x - y, meaning x \equiv y \pmod{n_1 n_2 \cdots n_k}.

Claim 3: The construction is explicit. There is a formula for x (involving modular inverses) that produces the solution directly, without any search.

Why the coprime hypothesis is non-negotiable: if \gcd(n_i, n_j) > 1 for some pair, the two congruences x \equiv a_i \pmod{n_i} and x \equiv a_j \pmod{n_j} have to agree on the remainder mod \gcd(n_i, n_j). If they disagree, the system has no solution at all. CRT avoids this by requiring coprimality up front.

The constructive formula

For two coprime moduli m, n with conditions x \equiv a \pmod m and x \equiv b \pmod n, the unique solution mod mn is

x \equiv a \cdot n \cdot (n^{-1} \bmod m) + b \cdot m \cdot (m^{-1} \bmod n) \pmod{mn}.

For the example above with a = 2, m = 3, b = 3, n = 5:

n^{-1} \bmod m: find the inverse of 5 mod 3. 5 \equiv 2 \pmod 3, and 2 \cdot 2 = 4 \equiv 1 \pmod 3, so 5^{-1} \equiv 2 \pmod 3.
m^{-1} \bmod n: find the inverse of 3 mod 5. 3 \cdot 2 = 6 \equiv 1 \pmod 5, so 3^{-1} \equiv 2 \pmod 5.

x \equiv 2 \cdot 5 \cdot 2 + 3 \cdot 3 \cdot 2 = 20 + 18 = 38 \equiv 8 \pmod{15}. \checkmark

Same answer as the trial-and-error search, by formula. For more than two moduli, apply the formula pairwise (or use its k-modulus generalisation).

Where CRT shows up that you might not expect

Chinese mathematics and astronomy. The name comes from the Sunzi Suanjing, a Chinese text that solves problems of the form "a general counts his troops in batches of 3 with 2 left over, batches of 5 with 3 left over…" The technique was independently developed in India by Aryabhata (499 CE), whose kuttaka method handles simultaneous remainder problems.
Cryptography. RSA decryption is often sped up using CRT: instead of computing c^d \bmod n directly (where n = pq is huge), compute c^d \bmod p and c^d \bmod q separately, then CRT them together. This is about 4\times faster.
Polynomial factorisation. The same theorem generalises to polynomials: a polynomial system with pairwise coprime factors has a unique solution modulo the product polynomial. This is the foundation of fast polynomial arithmetic in computer algebra.
Combinatorial counting. When a counting problem splits into cases classified by remainders mod p and mod q (for coprime p, q), CRT guarantees the cases combine uniquely mod pq without gaps or overlaps.

Find the smallest positive integer $x$ with $x \equiv 1 \pmod 4$, $x \equiv 2 \pmod 5$, and $x \equiv 3 \pmod 7$.

All three moduli are pairwise coprime (\gcd(4, 5) = \gcd(4, 7) = \gcd(5, 7) = 1), so CRT applies. Unique x \pmod{140}.

Start with the first two: x \equiv 1 \pmod 4 gives x \in \{1, 5, 9, 13, 17, \ldots\}. Which satisfy x \equiv 2 \pmod 5? Check 17 \bmod 5 = 2. ✓ So x \equiv 17 \pmod{20}.

Now add the third: x \equiv 17 \pmod{20} gives x \in \{17, 37, 57, 77, 97, \ldots\}. Which satisfies x \equiv 3 \pmod 7? Check 17 \bmod 7 = 3. ✓

So the smallest positive integer is x = 17, and the full solution set is x \equiv 17 \pmod{140}.

Why: the first modulus was satisfied by 17. By lucky numerical coincidence, 17 also satisfied the next two moduli — the theorem guarantees some solution but does not promise it will be this small. Larger systems routinely need the full construction.

Why it belongs near the start of number theory

CRT is not an advanced curiosity. It is the theorem that says coprime moduli compose cleanly. Every time you see a statement of the form "solve these separate modular conditions" or "a function mod mn decomposes into its reductions mod m and mod n separately," CRT is the reason. It is to modular arithmetic what factorisation into primes is to multiplication: the tool that lets you break a problem into independent pieces.

The even-shorter version

If you had to write CRT on the back of a napkin: coprime congruences combine into one, uniquely modulo the product of moduli. That is the whole theorem. Coprimality is the price. The uniqueness is the reward.