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

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

$\displaystyle x \equiv a_1 \pmod{n_1}, \quad
x \equiv a_2 \pmod{n_2}, \quad
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

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

$\displaystyle 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,

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

$\displaystyle 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,

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

so there exists integers $ x,y$ such that

$\displaystyle 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.

William Stein 2012-09-24