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 be positive integers that are pairwise relatively prime. Let be any integers. Then the following system of linear congruence equations
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 be positive integers that are pairwise relatively prime. Then for any integers and , the following linear congruences hold
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 .