TheoremProved

Chinese remainder theorem

Statement

If $n_1,\dots,n_k$ are pairwise coprime positive integers, then for any integers $a_1,\dots,a_k$ the system of congruences $x\equiv a_i \pmod{n_i}$ ( $i=1,\dots,k$ ) has a solution $x$ , unique modulo $N=n_1n_2\cdots n_k$ .

Why is it true?

Pairwise-coprime moduli carry independent information, so specifying a remainder for each one pins down a unique residue modulo their product — like reading off a single number from several clocks that run at coprime periods.

Proof sketch

For each $i$ let $N_i=N/n_i$ . Since $\gcd(N_i,n_i)=1$ , Bézout's identity gives $y_i$ with $N_iy_i\equiv1\pmod{n_i}$ . Then $x=\sum_i a_iN_iy_i$ satisfies $x\equiv a_i\pmod{n_i}$ for every $i$ , because $N_j\equiv0\pmod{n_i}$ for $j\ne i$ . Uniqueness modulo $N$ follows since two solutions must differ by a multiple of every $n_i$ , hence by a multiple of $N$ .

Proved by

proved 1801Carl Friedrich Gauss

Topics that use this theorem

Chinese remainder theorem

Related theorems

Bézout's identity

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Carl Friedrich Gauss (trans. Arthur A. Clarke) (1986). Disquisitiones Arithmeticae · DOI:10.1016/B978-044450871-3/50117-0
Jean-Claude Martzloff (1997). A History of Chinese Mathematics · DOI:10.1007/978-3-540-33783-6