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

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

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,

William Stein 2012-09-24