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,

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,

y_1=2.

Next,

21\equiv1\pmod5,

y_2=1.

Finally,

15\equiv1\pmod7,

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.