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 .

___________________________________________________________________________________________________________________