In this post, we consider systems of linear congruence equations with respect to pairwise relatively prime moduli. The theorem we prove here is known as the Chinese remainder theorem (see Theorem 1 below). It is useful in many contexts. For an example, see the blog post Introducing Carmichael numbers (used in proving the Korselt’s Criterion). Theorem 2 below is a useful corollary of the Chinese remainder theorem. For examples of applications, see Primitive roots of twice the powers of odd primes and The primitive root theorem (used in proving the primitive root theorem).
-
Theorem 1 (Chinese Remainder Theorem)
-
Let
has a solution .
Furthermore, is another solution to the above system of equations if and only if
.
Proof of Theorem 1
Let . For each
, let
. Note that
is the product of all
where
. So
and
are relatively prime. Thus for each
,
has a multiplicative inverse modulo
. Let
be the inverse of
. Now define
for each
.
It is clear that for each ,
for each
and
for all
. Now define
as the following:
It follows that for each
. Thus
is a solution that we are looking for.
It remains to show that solutions to the above system of equations are unique modulo . Suppose that
. This means that
for some integer
. It follows from this equation that
for each
. Thus
for each
.
On the other hand, suppose that is another solution to the above system of equations. Then
for each
. So
for each
. We have the following equations
for some integers . From these equations, it follows that
for some integer
. This is due to the fact that the integers
are relatively prime. For example, from the first two equations,
. Since
and
are relatively prime,
, we have
for some integer
. Then consider this new equation along with the third equation above, we have
. Because the integers
are pairwise relatively prime,
. So we can further factor
into
for some integer
. Continuing this process, we can obtain
. It follows that
.
-
Theorem 2 (Corollary of Chinese Remainder Theorem)
-
Let
if and only of .
Proof of Theorem 2
This is an easy consequence of Theorem 1. Let . Then
would be a solution to the resulting system of linear congruence equations in Theorem 1. Theorem 2 then follows from the fact that any other solution to the system is congruent to
modulo
.
___________________________________________________________________________________________________________________