## CRT in the Integers

The Chinese Remainder Theorem from elementary number theory asserts that if are integers that are coprime in pairs, and are integers, then there exists an integer  such that for each . Here coprime in pairs'' means that whenever ; it does not mean that , though it implies this. In terms of rings, the Chinese Remainder Theorem (CRT) asserts that the natural map

 (5.1)

that sends to its reduction modulo each , is an isomorphism.

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

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

with pairwise coprime moduli has a unique solution modulo .

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

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

If and are integers, then is the set of multiples of both and , so . Since the are coprime,

Thus we have proved there is an inclusion

 (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 is also surjective, because 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 , note that since the are coprime in pairs,

so there exists integers such that

To complete the proof, observe that is congruent to  modulo and 0 modulo . Thus is in the image of . By a similar argument, we see that and the other similar elements are all in the image of , so is surjective, which proves CRT.

William Stein 2012-09-24