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

$$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

$$(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$