Math Core

The Chinese remainder theorem (CRT) says that knowing a number mod $8$ and mod $125$ is the same as knowing it mod $1000$ . That turns one hard modulus into several easy ones. On the AIME, where every answer is a remainder mod $1000$ in disguise, this is one of the most-used tools you have.

The theorem

Chinese remainder theorem

If $m_1, m_2, \dots, m_k$ are pairwise relatively prime and $M = m_1 m_2 \cdots m_k$ , then for any remainders $r_1, \dots, r_k$ the system

$x \equiv r_1 \pmod{m_1}, \quad x \equiv r_2 \pmod{m_2}, \quad \dots, \quad x \equiv r_k \pmod{m_k}$

has a solution, and the solution is unique mod $M$ .

Why it's true (two moduli). Take $m, n$ with $\gcd(m, n) = 1$ and look at the $mn$ numbers $0, 1, \dots, mn - 1$ . Send each $x$ to its pair of remainders $(x \bmod m, \ x \bmod n)$ .

Different $x$ give different pairs. If $x$ and $y$ give the same pair, then $m \mid x - y$ and $n \mid x - y$ , so $mn \mid x - y$ (because $m, n$ are coprime). Since $|x - y| < mn$ , $x = y$ .
Every pair is hit. There are $mn$ inputs, all giving different pairs, and exactly $mn$ possible pairs.

So each pair of remainders corresponds to exactly one residue mod $mn$ . For more moduli, apply this repeatedly.

A constructive version. By Bézout, there are integers $u, v$ with $um + vn = 1$ . Then $x = r_2 um + r_1 vn$ works: mod $m$ it is $r_1 vn \equiv r_1$ (since $vn \equiv 1$ ), and mod $n$ it is $r_2 um \equiv r_2$ .

Solving systems in practice

On a contest you rarely need Bézout. Two faster methods:

Sieve. List numbers satisfying the congruence with the largest modulus, and test them against the next one. Once you find a match, step by the product of the moduli so far.
Substitute. From $x \equiv r_1 \pmod{m_1}$ write $x = r_1 + m_1 t$ , plug into the next congruence, and solve for $t$ .

Common mistake

CRT needs pairwise coprime moduli. If they share a factor, the system might have no solution: $x \equiv 1 \pmod 6$ and $x \equiv 2 \pmod 4$ is impossible, since the first says $x$ is odd and the second says $x$ is even. When the moduli share $g = \gcd(m, n)$ , a solution exists exactly when $r_1 \equiv r_2 \pmod g$ , and then it is unique mod $\operatorname{lcm}(m, n)$ , not mod $mn$ .

Counting with CRT

CRT also counts. If $f$ is a polynomial with integer coefficients, then $f(x) \equiv 0 \pmod{mn}$ exactly when $f(x) \equiv 0 \pmod m$ and $f(x) \equiv 0 \pmod n$ . So

$\#\{\text{solutions mod } mn\} = \#\{\text{solutions mod } m\} \times \#\{\text{solutions mod } n\}.$

For example, $x^2 \equiv 1 \pmod{1000}$ has $4$ solutions mod $8$ (every odd $x$ ) and $2$ mod $125$ ( $x \equiv \pm 1$ ), so $8$ solutions mod $1000$ .

Worked examples

Worked example: A basic system

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

Numbers $\equiv 2 \pmod 7$ : $2, 9, 16, 23, 30, \dots$ The first that is $\equiv 3 \pmod 5$ is $23$ . So $x \equiv 23 \pmod{35}$ . Check mod $3$ : $23 \equiv 2$ . It already works, so $x = 23$ .

Worked example: Splitting 1000

Find the last three digits of $2^{100}$ .

Mod $8$ : $2^{100} \equiv 0$ . Mod $125$ : by Euler, $2^{100} \equiv 1$ since $\varphi(125) = 100$ .

Now find $x \equiv 1 \pmod{125}$ with $8 \mid x$ : try $1, 126, 251, 376$ . Only $376$ is divisible by $8$ . The last three digits are $376$ .

Worked example: Consecutive numbers

Find the smallest positive $n$ such that $4 \mid n$ , $9 \mid n + 1$ and $25 \mid n + 2$ .

The conditions are $n \equiv 0 \pmod 4$ , $n \equiv 8 \pmod 9$ , $n \equiv 23 \pmod{25}$ .

Numbers $\equiv 23 \pmod{25}$ : $23, 48, 73, 98, \dots$ Those also $\equiv 0 \pmod 4$ : $48$ is the first, so $n \equiv 48 \pmod{100}$ . Now test $48, 148, 248, \dots$ mod $9$ (digit sums $12, 13, 14, \dots$ so remainders $3, 4, 5, 6, 7, 8$ ): the sixth one, $548$ , works.

Check: $548 = 4 \cdot 137$ , $549 = 9 \cdot 61$ , $550 = 25 \cdot 22$ . So $n = 548$ .

Worked example: Moduli that aren't coprime

Solve $x \equiv 5 \pmod{12}$ and $x \equiv 11 \pmod{18}$ .

Here $\gcd(12, 18) = 6$ . The system is consistent because $5 \equiv 11 \pmod 6$ . The solution is unique mod $\operatorname{lcm}(12, 18) = 36$ . Numbers $\equiv 5 \pmod{12}$ below $36$ : $5, 17, 29$ . Only $29$ is $\equiv 11 \pmod{18}$ . So $x \equiv 29 \pmod{36}$ .

Tip

When a remainder condition looks like " $n + 1$ is divisible by $2, 3, 4, 5, 6$ ", rewrite it as $n \equiv -1$ modulo the lcm. Negative remainders often make systems collapse into one congruence.

Practice

Practice 1

Find the smallest positive integer that leaves remainder $2$ when divided by $5$ , remainder $3$ when divided by $7$ , and remainder $4$ when divided by $9$ .