Unipal Initiative - Free Competition Math Courses, From Students For Students

The Chinese Remainder Theorem (CRT) says that a system of congruences with pairwise coprime moduli always has a solution, and that solution is unique modulo the product of the moduli:

x \equiv r_1 \pmod{m_1}, \quad x \equiv r_2 \pmod{m_2}, \quad \ldots

has a unique solution modulo $m_1 \cdot m_2 \cdots$ (given the $m_i$ are pairwise coprime).

The practical method

You rarely need the general CRT formula on a contest — it’s usually faster to solve incrementally: take the first congruence, and among the numbers satisfying it, substitute into the second congruence to narrow down further, repeating until all conditions are satisfied.

Worked example

Problem: Find the smallest positive integer $x$ such that $x \equiv 2 \pmod 3$ and $x \equiv 3 \pmod 5$ .

Solution: Numbers satisfying $x \equiv 2 \pmod 3$ : $2, 5, 8, 11, 14, \ldots$ (each is $3k+2$ ). Test these against the second condition $x \equiv 3 \pmod 5$ :

2\bmod5=2 \ \times,\quad 5\bmod5=0 \ \times,\quad 8\bmod5=3\ \checkmark

So $x=8$ works. By CRT, since $\gcd(3,5)=1$ , the full solution set is $x \equiv 8 \pmod{15}$ — every 15th integer after 8 also works.

Practice problems

1.Find the smallest positive integer with $x\equiv1\pmod4$ and $x\equiv2\pmod5$ .

2.Given $x\equiv2\pmod3$ and $x\equiv4\pmod7$ , find the general solution modulo $21$ .

3.Find the smallest positive integer satisfying $x\equiv1\pmod2$ , $x\equiv2\pmod3$ , and $x\equiv3\pmod5$ .

4.Why does CRT require the moduli to be pairwise coprime?