Chinese Remainder Theorem

Independent Congruence Conditions

The Chinese remainder theorem describes when several congruence conditions can be combined into one congruence. Its cleanest form occurs when the moduli are pairwise coprime.

Suppose

$$ n_1,n_2,\ldots,n_r $$

are positive integers satisfying

$$ \gcd(n_i,n_j)=1 $$

whenever

$$ i\ne j. $$

Then the congruences

$$ x\equiv a_1\pmod{n_1}, $$

$$ x\equiv a_2\pmod{n_2}, $$

$$ \cdots $$

$$ x\equiv a_r\pmod{n_r} $$

have a unique solution modulo

$$ N=n_1n_2\cdots n_r. $$

This means all integer solutions form exactly one residue class modulo $N$.

The Case of Two Moduli

First consider

$$ x\equiv a\pmod m, $$

$$ x\equiv b\pmod n, $$

where

$$ \gcd(m,n)=1. $$

Write

$$ x=a+mk. $$

Substituting into the second congruence gives

$$ a+mk\equiv b\pmod n. $$

Thus

$$ mk\equiv b-a\pmod n. $$

Since

$$ \gcd(m,n)=1, $$

the integer $m$ has an inverse modulo $n$. Therefore this linear congruence has a unique solution modulo $n$. Once $k$ is determined, $x=a+mk$ gives a solution to the original system.

The solution is unique modulo $mn$.

Example

Solve

$$ x\equiv2\pmod3, $$

$$ x\equiv3\pmod5. $$

Write

$$ x=2+3k. $$

Then

$$ 2+3k\equiv3\pmod5, $$

so

$$ 3k\equiv1\pmod5. $$

Since

$$ 3^{-1}\equiv2\pmod5, $$

we get

$$ k\equiv2\pmod5. $$

Thus

$$ k=2+5t. $$

Hence

$$ x=2+3(2+5t)=8+15t. $$

Therefore

$$ x\equiv8\pmod{15}. $$

Constructive Formula

The theorem also has an explicit constructive formula.

Let

$$ N=n_1n_2\cdots n_r. $$

For each $i$, define

$$ N_i=\frac{N}{n_i}. $$

Since the moduli are pairwise coprime,

$$ \gcd(N_i,n_i)=1. $$

Therefore $N_i$ has an inverse modulo $n_i$. Choose $y_i$ such that

$$ N_i y_i\equiv1\pmod{n_i}. $$

Then a solution is

$$ x\equiv \sum_{i=1}^{r} a_iN_iy_i \pmod N. $$

To see why, reduce this expression modulo $n_j$. If $i\ne j$, then $n_j\mid N_i$, so

$$ a_iN_iy_i\equiv0\pmod{n_j}. $$

Only the $j$-th term remains:

$$ x\equiv a_jN_jy_j\equiv a_j\pmod{n_j}. $$

Thus the formula satisfies every congruence.

Example with Three Moduli

Solve

$$ x\equiv2\pmod3, $$

$$ x\equiv3\pmod5, $$

$$ x\equiv2\pmod7. $$

The moduli are pairwise coprime, and

$$ N=3\cdot5\cdot7=105. $$

Compute

$$ N_1=35, \qquad N_2=21, \qquad N_3=15. $$

Now find inverses:

$$ 35\equiv2\pmod3, $$

and

$$ 2^{-1}\equiv2\pmod3, $$

so

$$ y_1=2. $$

Next,

$$ 21\equiv1\pmod5, $$

so

$$ y_2=1. $$

Finally,

$$ 15\equiv1\pmod7, $$

so

$$ y_3=1. $$

Therefore

$$ x\equiv 2\cdot35\cdot2 + 3\cdot21\cdot1 + 2\cdot15\cdot1 \pmod{105}. $$

This gives

$$ x\equiv140+63+30=233\pmod{105}. $$

Since

$$ 233\equiv23\pmod{105}, $$

the solution is

$$ x\equiv23\pmod{105}. $$

Uniqueness

Suppose $x$ and $x'$ both solve the same system. Then for every $i$,

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

Thus

$$ n_i\mid(x-x') $$

for each $i$.

Since the $n_i$ are pairwise coprime, their product divides $x-x'$:

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

Therefore

$$ x\equiv x'\pmod N. $$

This proves uniqueness modulo $N$.

Ring Form

The Chinese remainder theorem can be expressed as an isomorphism of rings:

$$ \mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z} \times \cdots \times \mathbb{Z}/n_r\mathbb{Z}, $$

where

$$ N=n_1n_2\cdots n_r $$

and the moduli are pairwise coprime.

The map sends a residue class $[x]_N$ to

$$ ([x]{n_1},[x]{n_2},\ldots,[x]_{n_r}). $$

The theorem says this map is bijective and respects addition and multiplication.

General Compatibility

If the moduli are not pairwise coprime, a system may still have solutions, but compatibility conditions are required.

The system

$$ x\equiv a_i\pmod{n_i} $$

is solvable exactly when

$$ a_i\equiv a_j\pmod{\gcd(n_i,n_j)} $$

for every pair $i,j$.

When solvable, the solution is unique modulo

$$ \operatorname{lcm}(n_1,n_2,\ldots,n_r). $$

Thus the pairwise coprime case is the special case where all compatibility conditions are automatic.

Role in Number Theory

The Chinese remainder theorem shows that arithmetic modulo a product of coprime moduli decomposes into independent arithmetic modulo each factor.

This principle is fundamental in modular arithmetic, computation, cryptography, algebraic number theory, and local-global reasoning.

It lets one replace a difficult congruence modulo $N$ by several simpler congruences modulo the prime-power factors of $N$. This is one of the main ways number theory breaks a global problem into local pieces.