Chinese Remainder Theorem: Statement and Proof

students, imagine you are trying to coordinate several clocks that all reset at different intervals ⏰. One clock rings every $3$ hours, another every $5$ hours, and a third every $7$ hours. If you know the reminder pattern for each one, can you find a single time that matches them all? The Chinese Remainder Theorem gives the answer: under the right conditions, a system of congruences has a solution, and that solution is unique modulo the product of the moduli.

In this lesson, you will learn how to state the theorem clearly, understand the meaning of its conditions, and follow the proof idea step by step. By the end, you should be able to explain why the theorem works and how it fits into the larger topic of Chinese Remainder Theorem methods in Number Theory.

What the theorem says

The Chinese Remainder Theorem is about solving several congruences at the same time. A typical system looks like this:

$\begin{aligned}$

$ x &\equiv a_1 \pmod{m_1} \\$

$ x &\equiv a_2 \pmod{m_2} \\$

$ &\,\vdots \\$

$ x &\equiv a_k \pmod{m_k}$

$\end{aligned}$

Here, $x$ is the unknown integer, each $a_i$ is a remainder, and each $m_i$ is a modulus. The key condition is that the moduli are pairwise coprime, meaning

\gcd(m_i,m_j)=1 \quad \text{for all } i$\neq$ j.

That means no two moduli share a common factor greater than $1$. For example, $3$, $4$, and $5$ are pairwise coprime, but $4$ and $6$ are not because $\gcd(4,6)=2$.

A clean statement of the theorem is this:

If $m_1,m_2,\dots,m_k$ are pairwise coprime positive integers, then for any integers $a_1,a_2,\dots,a_k$, the system above has a solution. Also, that solution is unique modulo

$M=m_1m_2\cdots m_k.$

“Unique modulo $M$” means that if $x$ and $y$ are both solutions, then

$ x\equiv y \pmod{M}.$

So there may be many integer answers, but they all belong to one congruence class mod $M$.

Why the condition matters

students, the pairwise coprime condition is not just a technical detail; it is what makes the theorem work. If the moduli do not share factors, then the congruences do not interfere with one another in a harmful way.

Here is a quick example with pairwise coprime moduli:

x$\equiv 2$ \pmod{3}, \quad x$\equiv 3$ \pmod{4}, \quad x$\equiv 1$ \pmod{5}.

These can all be satisfied at once. One solution is $x=11$, because

$11\equiv 2$ \pmod{3}, \quad 11$\equiv 3$ \pmod{4}, \quad 11$\equiv 1$ \pmod{5}.

Now compare that with a system where the moduli are not coprime:

x$\equiv 1$ \pmod{2}, \quad x$\equiv 0$ \pmod{4}.

This system has no solution, because numbers congruent to $0$ mod $4$ are even, while numbers congruent to $1$ mod $2$ are odd. The conditions clash. So the theorem needs pairwise coprime moduli to guarantee both existence and uniqueness modulo $M$.

Proof idea: building a solution

The proof is constructive, which means it actually shows how to build the solution. The main trick is to create numbers that behave like switches: one piece turns on for one congruence and turns off for the others 🔧.

Let

$M=m_1m_2\cdots m_k.$

For each $i$, define

$M_i=\frac{M}{m_i}.$

Because the moduli are pairwise coprime, $M_i$ shares no factor with $m_i$. Therefore,

$\gcd(M_i,m_i)=1.$

This is important because it means $M_i$ has a multiplicative inverse modulo $m_i$. In other words, there exists an integer $y_i$ such that

$M_i y_i \equiv 1 \pmod{m_i}.$

You can find such a $y_i$ using the Euclidean Algorithm, which proves that the inverse exists.

Now define

$ e_i=M_i y_i.$

These numbers have a very useful property:

modulo $m_i$, we get $e_i\equiv 1$,
modulo $m_j$ for $j\neq i$, we get $e_i\equiv 0$ because $M_i$ contains the factor $m_j$.

So each $e_i$ acts like a selector for the $i$-th congruence.

Now set

$ x=a_1e_1+a_2e_2+\cdots+a_ke_k.$

Check what happens modulo $m_i$:

$ x\equiv a_1e_1+a_2e_2+\cdots+a_ke_k \pmod{m_i}.$

All terms except $a_ie_i$ are $0$ mod $m_i$, and $e_i\equiv 1$ mod $m_i$, so

$ x\equiv a_i \pmod{m_i}.$

This works for every $i$, so the constructed $x$ solves the entire system.

Proof of uniqueness modulo $M$

Now students, let’s prove the “unique modulo $M$” part. Suppose $x$ and $x'$ are both solutions. Then for each $i$,

x$\equiv$ a_i \pmod{m_i} \quad \text{and} \quad x'$\equiv$ a_i \pmod{m_i}.

Subtracting these gives

$ x-x'\equiv 0 \pmod{m_i}$

for every $i$. That means each $m_i$ divides $x-x'$.

Because the $m_i$ are pairwise coprime, their product also divides $x-x'$:

$M\mid (x-x').$

$ x\equiv x' \pmod{M}.$

That is exactly the uniqueness claim. There is only one solution class modulo $M$.

This part of the proof shows a powerful number theory idea: if several pairwise coprime numbers each divide the same integer, then their product divides it too. This result is a key reason the theorem works so cleanly.

A worked example of the proof method

Let’s use the proof method on a concrete system:

x$\equiv 2$ \pmod{3}, \quad x$\equiv 3$ \pmod{4}, \quad x$\equiv 1$ \pmod{5}.

First compute the product:

$M=3\cdot 4\cdot 5=60.$

Then compute each $M_i$:

$M_1=20, \quad M_2=15, \quad M_3=12.$

Next find inverses:

$20\equiv 2 \pmod{3}$, and $2\cdot 2\equiv 1 \pmod{3}$, so $y_1=2$.
$15\equiv 3 \pmod{4}$, and $3\cdot 3\equiv 1 \pmod{4}$, so $y_2=3$.
$12\equiv 2 \pmod{5}$, and $2\cdot 3\equiv 1 \pmod{5}$, so $y_3=3$.

Now build the solution:

$ x=2(20)(2)+3(15)(3)+1(12)(3).$

This simplifies to

$ x=80+135+36=251.$

To find the smallest positive solution, reduce modulo $60$:

$251\equiv 11 \pmod{60}.$

So $x=11$ is the solution class. This matches the earlier check.

How the proof fits the whole topic

The statement and proof are the foundation of the Chinese Remainder Theorem. Once you understand why the theorem is true, the rest of the topic becomes easier to use.

The proof explains three major ideas:

Existence: a solution can be built.
Uniqueness modulo $M$: all solutions belong to one congruence class.
Construction: the solution can be made explicitly using inverses and the numbers $M_i$.

These ideas lead directly to applications such as simplifying large modular calculations, solving puzzles, and working with remainders in encryption and coding theory. The theorem is not just a fact to memorize; it is a tool for organizing many remainder conditions into one answer.

Conclusion

students, the Chinese Remainder Theorem says that when the moduli are pairwise coprime, a system of congruences has a solution, and that solution is unique modulo the product of the moduli. The proof works by building special numbers using $M_i=\frac{M}{m_i}$ and modular inverses, then combining them into one answer. The uniqueness part follows because any two solutions differ by a multiple of every modulus, and therefore by a multiple of their product.

Understanding the statement and proof helps you see why the theorem is true, not just how to use it. That makes it easier to solve problems confidently and connect this topic to the broader world of Number Theory 📘.

Study Notes

The Chinese Remainder Theorem applies to congruences with pairwise coprime moduli.
Pairwise coprime means $\gcd(m_i,m_j)=1$ for every $i\neq j$.
If $M=m_1m_2\cdots m_k$, then the solution is unique modulo $M$.
The proof uses $M_i=\frac{M}{m_i}$ and modular inverses of $M_i$ modulo $m_i$.
A modular inverse of $M_i$ modulo $m_i$ is an integer $y_i$ satisfying $M_i y_i\equiv 1\pmod{m_i}$.
The constructed solution is

$ x=\sum_{i=1}^{k} a_i M_i y_i.$

To prove uniqueness, subtract two solutions and use divisibility by each $m_i$.
The theorem is a major tool for solving simultaneous remainder problems in Number Theory.