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$