General Chinese remainder theorem

Theorem 1.7.35 (Chinese remainder theorem, general version)   Let $ n_1>1, n_2>1,...,n_k>1$ be pairwise relatively prime integers. Let $ n=n_1n_2...n_k$. Then

$\displaystyle x\equiv a_1\ ({\rm mod}\ n_1),\ x\equiv a_2\ ({\rm mod}\ n_2),..., x\equiv a_k\ ({\rm mod}\ n_k)$ (1.7)

has a simultaneous solution $ x\in \mathbb{Z}$. Furthermore, if $ x,x'$ are two solutions to (1.7) then $ x'\equiv x\ ({\rm mod}\ n)$.

This follows from the $ k=2$ case proven above using mathematical induction. The details are left as an exercise. We give a different proof below.

proof: As $ a$ runs over all $ n$ integers $ 0\leq a<n$, the $ k$-tuples

$\displaystyle (a\ ({\rm mod}\ n_1),..., a\ ({\rm mod}\ n_k)) $

form a collection of $ n$ distinct $ k$-tuples in $ \{0,1,...,n-1\}^k$. (Exercise: show why they are distinct.) On the other hand, there are $ n$ distinct, $ k$-tuples $ (a_1,a_2,...,a_k)$ with $ 0\leq a_i <n_i$. Therefore, each $ k$-tuple $ (a_1,a_2,...,a_k)$ must equal one of the $ (a\ ({\rm mod}\ n_1),...,a\ ({\rm mod}\ n_k))$, for $ 0\leq a<n$. $ \Box$


David Joyner 2007-09-03