Number TheoryDifficulty 35-85209 tagged problems

Chinese Remainder Theorem

Chinese Remainder Theorem is the habit of combining compatible congruences into one residue class modulo a product. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\begin{cases} x \equiv a_1 \pmod{m_1} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases} \text{ has a unique solution mod } m_1 \cdots m_k \text{ when the } m_i \text{ are pairwise coprime}$$

Congruences with pairwise coprime moduli can always be combined into a single congruence modulo the product, and that combined residue is unique.

Why It Works

1
Let $M = m_1 m_2 \cdots m_k$ and $M_i = M / m_i$, so $\gcd(M_i, m_i) = 1$ because the moduli are pairwise coprime.
2
By Bézout each $M_i$ has an inverse $y_i$ mod $m_i$, meaning $M_i y_i \equiv 1 \pmod{m_i}$.
3
Set $x = \sum_i a_i M_i y_i$; modulo $m_i$ every term with $j \neq i$ vanishes (as $m_i \mid M_j$), leaving $x \equiv a_i M_i y_i \equiv a_i \pmod{m_i}$.
4
If two solutions agree on all $m_i$, their difference is divisible by each $m_i$, hence by $M$, giving uniqueness mod $M$.

Worked Examples

Example 1

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

1
The moduli $3, 5, 7$ are pairwise coprime, so a unique answer exists mod $105$.
2
From $x \equiv 2 \pmod 3$ and $x \equiv 2 \pmod 7$: numbers $\equiv 2$ mod both are $\equiv 2 \pmod{21}$, so $x = 21t + 2$.
3
Impose $x \equiv 3 \pmod 5$: $21t + 2 \equiv t + 2 \equiv 3 \pmod 5$, so $t \equiv 1 \pmod 5$; take $t = 1$.
4
Then $x = 21 \cdot 1 + 2 = 23$. Check all three: $23 \equiv 2 \pmod 3$, $23 \equiv 3 \pmod 5$, and $23 \equiv 2 \pmod 7$.

Answer:

$23$

Warm-up

Find the smallest positive integer $x$ with $x \equiv 1 \pmod 4$ and $x \equiv 2 \pmod 9$.

1
Moduli $4$ and $9$ are coprime, so a unique solution exists mod $36$.
2
From $x \equiv 1 \pmod 4$, write $x = 4k + 1$.
3
Impose $x \equiv 2 \pmod 9$: $4k + 1 \equiv 2 \pmod 9$, so $4k \equiv 1 \pmod 9$. Since $4 \cdot 7 = 28 \equiv 1 \pmod 9$, the inverse of $4$ is $7$, giving $k \equiv 7 \pmod 9$.
4
Take $k = 7$: $x = 4 \cdot 7 + 1 = 29$. Check: $29 = 7\cdot4 + 1$ and $29 = 3\cdot9 + 2$. ✓

Answer:

$29$

Contest level

Find the remainder when $3^{100}$ is divided by $35$.

1
$35 = 5 \cdot 7$ with $\gcd(5,7) = 1$, so compute $3^{100}$ mod $5$ and mod $7$ separately, then recombine via CRT.
2
Mod $5$: by Fermat $3^4 \equiv 1$, and $100 = 4 \cdot 25$, so $3^{100} \equiv 1 \pmod 5$.
3
Mod $7$: $3^6 \equiv 1$, and $100 = 6 \cdot 16 + 4$, so $3^{100} \equiv 3^4 = 81 \equiv 4 \pmod 7$.
4
Solve $x \equiv 1 \pmod 5$, $x \equiv 4 \pmod 7$: try $x = 7m + 4 \equiv 2m + 4 \equiv 1 \pmod 5 \Rightarrow 2m \equiv 2 \Rightarrow m \equiv 1$, so $x = 7 + 4 = 11$. Check: $11 \equiv 1 \pmod 5$, $11 \equiv 4 \pmod 7$. ✓

Answer:

$11$

Olympiad / Challenge

Prove that there exist $100$ consecutive positive integers, none of which is squarefree (each divisible by some perfect square $> 1$).

1
Choose $100$ distinct primes $p_1, p_2, \dots, p_{100}$. The moduli $p_1^2, p_2^2, \dots, p_{100}^2$ are pairwise coprime.
2
By the Chinese Remainder Theorem, the system $x \equiv -i \pmod{p_i^2}$ for $i = 1, \dots, 100$ has a solution $x = N$ (and infinitely many positive ones).
3
Then $N + i \equiv 0 \pmod{p_i^2}$, so $p_i^2 \mid (N + i)$ for each $i = 1, \dots, 100$.
4
Hence $N+1, N+2, \dots, N+100$ are $100$ consecutive integers, each divisible by a perfect square $> 1$, so none is squarefree.

Answer:

Such a run exists — CRT plants a square factor at each of $100$ consecutive positions.

Going Deeper

Generalization: CRT is an isomorphism $\mathbb{Z}/m_1\cdots m_k \cong \mathbb{Z}/m_1 \times \cdots \times \mathbb{Z}/m_k$ when the moduli are pairwise coprime, so any computation mod a composite $n$ can be done independently on each prime-power factor and reassembled. This is why multiplicative functions like $\varphi$, $\tau$, $\sigma$ split across coprime factors.
Where it appears: computing $a^N \bmod n$ by splitting $n$ into prime powers, counting solutions of $f(x) \equiv 0 \pmod n$ (multiply the counts mod each prime power), 'find $N$ consecutive integers with property $P$' constructions, and calendar/clock remainder puzzles.
Pitfall: CRT REQUIRES pairwise coprime moduli. With a shared factor a system may have no solution or many — e.g. $x \equiv 1 \pmod 4$ and $x \equiv 2 \pmod 6$ is inconsistent (they disagree mod $2$). For non-coprime moduli, check consistency $a_i \equiv a_j \pmod{\gcd(m_i, m_j)}$ first, then the solution is unique mod $\operatorname{lcm}$, not the product.

Spot the Signal

Look for problems where the key step is combining compatible congruences into one residue class modulo a product.
You can describe the hard part as combining compatible congruences into one residue class modulo a product, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for chinese remainder theorem, then rewrite the givens around it.
Name the relation that makes Chinese Remainder Theorem legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Chinese Remainder Theorem just because the surface looks familiar; verify the required condition first.
Applying Chinese Remainder Theorem because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let chinese remainder theorem reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is combining compatible congruences into one residue class modulo a product.

Back to techniques

Number TheoryDifficulty 35-85209 tagged problems

Chinese Remainder Theorem

Practice this technique Match my level

The Key Result

$$\begin{cases} x \equiv a_1 \pmod{m_1} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases} \text{ has a unique solution mod } m_1 \cdots m_k \text{ when the } m_i \text{ are pairwise coprime}$$

Congruences with pairwise coprime moduli can always be combined into a single congruence modulo the product, and that combined residue is unique.

Why It Works

1
Let $M = m_1 m_2 \cdots m_k$ and $M_i = M / m_i$, so $\gcd(M_i, m_i) = 1$ because the moduli are pairwise coprime.
2
By Bézout each $M_i$ has an inverse $y_i$ mod $m_i$, meaning $M_i y_i \equiv 1 \pmod{m_i}$.
3
Set $x = \sum_i a_i M_i y_i$; modulo $m_i$ every term with $j \neq i$ vanishes (as $m_i \mid M_j$), leaving $x \equiv a_i M_i y_i \equiv a_i \pmod{m_i}$.
4
If two solutions agree on all $m_i$, their difference is divisible by each $m_i$, hence by $M$, giving uniqueness mod $M$.

Worked Examples

Example 1

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

1
The moduli $3, 5, 7$ are pairwise coprime, so a unique answer exists mod $105$.
2
From $x \equiv 2 \pmod 3$ and $x \equiv 2 \pmod 7$: numbers $\equiv 2$ mod both are $\equiv 2 \pmod{21}$, so $x = 21t + 2$.
3
Impose $x \equiv 3 \pmod 5$: $21t + 2 \equiv t + 2 \equiv 3 \pmod 5$, so $t \equiv 1 \pmod 5$; take $t = 1$.
4
Then $x = 21 \cdot 1 + 2 = 23$. Check all three: $23 \equiv 2 \pmod 3$, $23 \equiv 3 \pmod 5$, and $23 \equiv 2 \pmod 7$.

Answer:

$23$

Warm-up

Find the smallest positive integer $x$ with $x \equiv 1 \pmod 4$ and $x \equiv 2 \pmod 9$.

1
Moduli $4$ and $9$ are coprime, so a unique solution exists mod $36$.
2
From $x \equiv 1 \pmod 4$, write $x = 4k + 1$.
3
Impose $x \equiv 2 \pmod 9$: $4k + 1 \equiv 2 \pmod 9$, so $4k \equiv 1 \pmod 9$. Since $4 \cdot 7 = 28 \equiv 1 \pmod 9$, the inverse of $4$ is $7$, giving $k \equiv 7 \pmod 9$.
4
Take $k = 7$: $x = 4 \cdot 7 + 1 = 29$. Check: $29 = 7\cdot4 + 1$ and $29 = 3\cdot9 + 2$. ✓

Answer:

$29$

Contest level

Find the remainder when $3^{100}$ is divided by $35$.

1
$35 = 5 \cdot 7$ with $\gcd(5,7) = 1$, so compute $3^{100}$ mod $5$ and mod $7$ separately, then recombine via CRT.
2
Mod $5$: by Fermat $3^4 \equiv 1$, and $100 = 4 \cdot 25$, so $3^{100} \equiv 1 \pmod 5$.
3
Mod $7$: $3^6 \equiv 1$, and $100 = 6 \cdot 16 + 4$, so $3^{100} \equiv 3^4 = 81 \equiv 4 \pmod 7$.
4
Solve $x \equiv 1 \pmod 5$, $x \equiv 4 \pmod 7$: try $x = 7m + 4 \equiv 2m + 4 \equiv 1 \pmod 5 \Rightarrow 2m \equiv 2 \Rightarrow m \equiv 1$, so $x = 7 + 4 = 11$. Check: $11 \equiv 1 \pmod 5$, $11 \equiv 4 \pmod 7$. ✓

Answer:

$11$

Olympiad / Challenge

Prove that there exist $100$ consecutive positive integers, none of which is squarefree (each divisible by some perfect square $> 1$).

1
Choose $100$ distinct primes $p_1, p_2, \dots, p_{100}$. The moduli $p_1^2, p_2^2, \dots, p_{100}^2$ are pairwise coprime.
2
By the Chinese Remainder Theorem, the system $x \equiv -i \pmod{p_i^2}$ for $i = 1, \dots, 100$ has a solution $x = N$ (and infinitely many positive ones).
3
Then $N + i \equiv 0 \pmod{p_i^2}$, so $p_i^2 \mid (N + i)$ for each $i = 1, \dots, 100$.
4
Hence $N+1, N+2, \dots, N+100$ are $100$ consecutive integers, each divisible by a perfect square $> 1$, so none is squarefree.

Answer:

Such a run exists — CRT plants a square factor at each of $100$ consecutive positions.

Going Deeper

Generalization: CRT is an isomorphism $\mathbb{Z}/m_1\cdots m_k \cong \mathbb{Z}/m_1 \times \cdots \times \mathbb{Z}/m_k$ when the moduli are pairwise coprime, so any computation mod a composite $n$ can be done independently on each prime-power factor and reassembled. This is why multiplicative functions like $\varphi$, $\tau$, $\sigma$ split across coprime factors.
Where it appears: computing $a^N \bmod n$ by splitting $n$ into prime powers, counting solutions of $f(x) \equiv 0 \pmod n$ (multiply the counts mod each prime power), 'find $N$ consecutive integers with property $P$' constructions, and calendar/clock remainder puzzles.
Pitfall: CRT REQUIRES pairwise coprime moduli. With a shared factor a system may have no solution or many — e.g. $x \equiv 1 \pmod 4$ and $x \equiv 2 \pmod 6$ is inconsistent (they disagree mod $2$). For non-coprime moduli, check consistency $a_i \equiv a_j \pmod{\gcd(m_i, m_j)}$ first, then the solution is unique mod $\operatorname{lcm}$, not the product.

Spot the Signal

Look for problems where the key step is combining compatible congruences into one residue class modulo a product.
You can describe the hard part as combining compatible congruences into one residue class modulo a product, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for chinese remainder theorem, then rewrite the givens around it.
Name the relation that makes Chinese Remainder Theorem legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Chinese Remainder Theorem just because the surface looks familiar; verify the required condition first.
Applying Chinese Remainder Theorem because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let chinese remainder theorem reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is combining compatible congruences into one residue class modulo a product.