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
Here ``coprime in pairs'' means that
; it does not mean that
though it implies this.
In terms of rings, the Chinese Remainder Theorem (CRT) asserts that the
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
, 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
There is a natural map
given by projection onto each factor. It's kernel is
If and are integers, then
set of multiples of both and , so
Since the are coprime,
Thus we have proved there is an inclusion
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
so there exists integers
To complete the proof, observe that
is congruent to modulo and 0 modulo
is in the image of .
By a similar argument, we see that
other similar elements are all in the image of , so
is surjective, which proves CRT.