# 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.