CRT in the Integers

The Chinese Remainder Theorem from elementary number theory asserts that if $n_1,\ldots, n_r$ are integers that are coprime in pairs, and $a_1,\ldots, a_r$ are integers, then there exists an integer $a$ such that $a\equiv a_i\pmod{n_i}$ for each $i=1,\ldots,r$. Here ``coprime in pairs'' means that $\gcd(n_i,n_j)=1$ whenever $i\neq j$; it does not mean that $\gcd(n_1,\ldots, n_r)=1$, though it implies this. In terms of rings, the Chinese Remainder Theorem (CRT) asserts that the natural map

$$\mathbf{Z}/(n_1\cdots n_r)\mathbf{Z}\to (\mathbf{Z}/n_1\mathbf{Z})\oplus \cdots \oplus (\mathbf{Z}/n_r\mathbf{Z})$$ (5.1)

that sends $a \in \mathbf{Z}$ to its reduction modulo each $n_i$, is an isomorphism.

This map is not an isomorphism if the $n_i$ are not coprime. Indeed, the cardinality of the image of the left hand side of (5.1.1) is $\lcm (n_1,\ldots, n_r)$, since it is the image of a cyclic group and $\lcm (n_1,\ldots, n_r)$ is the largest order of an element of the right hand side, whereas the cardinality of the right hand side is $n_1\cdots n_r$.

The isomorphism (5.1.1) can alternatively be viewed as asserting that any system of linear congruences

$$x \equiv a_1 \pmod{n_1}, \quad x \equiv a_2 \pmod{n_2}, \quad \cdots, x \equiv a_r \pmod{n_r}$$

with pairwise coprime moduli has a unique solution modulo $n_1\ldots n_r$.

Before proving the CRT in more generalize, we prove (5.1.1). There is a natural map

$$\phi: \mathbf{Z}\to (\mathbf{Z}/n_1\mathbf{Z})\oplus \cdots \oplus (\mathbf{Z}/n_r\mathbf{Z})$$

given by projection onto each factor. It's kernel is

$$n_1 \mathbf{Z}\cap \cdots \cap n_r \mathbf{Z}.$$

If $n$ and $m$ are integers, then $n\mathbf{Z}\cap m\mathbf{Z}$ is the set of multiples of both $n$ and $m$, so $n\mathbf{Z}\cap m\mathbf{Z}= \lcm (n,m)\mathbf{Z}$. Since the $n_i$ are coprime,

$$n_1 \mathbf{Z}\cap \cdots \cap n_r \mathbf{Z}= n_1 \ldots n_r \mathbf{Z}.$$

Thus we have proved there is an inclusion

$$i: \mathbf{Z}/(n_1\cdots n_r)\mathbf{Z}\hookrightarrow (\mathbf{Z}/n_1\mathbf{Z})\oplus \cdots \oplus (\mathbf{Z}/n_r\mathbf{Z}).$$ (5.2)

This is half of the CRT; the other half is to prove that this map is surjective. In this case, it is clear that $i$ is also surjective, because $i$ is an injective map between sets of the same cardinality. We will, however, give a proof of surjectivity that doesn't use finiteness of the above two sets.

To prove surjectivity of $i$, note that since the $n_i$ are coprime in pairs,

$$\gcd(n_1, n_2\ldots n_r)=1,$$

so there exists integers $x,y$ such that

$$x n_1 + y n_2\cdots n_r = 1.$$

To complete the proof, observe that $y n_2\cdots n_r = 1 - x n_1$ is congruent to $1$ modulo $n_1$ and 0 modulo $n_2\cdots n_r$. Thus $(1,0,\ldots,0) = i (y n_2\cdots n_r)$ is in the image of $i$. By a similar argument, we see that $(0,1,\ldots,0)$ and the other similar elements are all in the image of $i$, so $i$ is surjective, which proves CRT.