# 3.4 The Chinese Remainder Theorem

In many situations, it is useful to break a congruence mod  into a system of congruences mod factors of  Consider the following example. Suppose we know that a number  satisfies  This means that we can write  for some integer  Rewriting 42 as  we obtain  which implies that  Similarly, since  we have  Therefore,



The Chinese remainder theorem shows that this process can be reversed; namely, a system of congruences can be replaced by a single congruence under certain conditions.

# Chinese Remainder Theorem

Suppose  Given integers  and  there exists exactly one solution  to the simultaneous congruences



Proof. There exist integers  such that  Then  and  Let  Then  and  so a solution  exists. Suppose  is another solution. Then  and  so  is a multiple of both  and 

# Lemma

Let  be integers with  If an integer  is a multiple of both  and  then  is a multiple of 

Proof. Let  Write  with integers  Multiply by  to obtain 

To finish the proof of the theorem, let  in the lemma to find that  is a multiple of  Therefore,  This means that any two solutions  to the system of congruences are congruent mod  as claimed.

# Example

Solve 

SOLUTION

 (note: ). Since  and  80 is a solution. The theorem guarantees that such a solution exists, and says that it is uniquely determined mod the product  which is 105 in the present example.

How does one find the solution? One way, which works with small numbers  and  is to list the numbers congruent to  until you find one that is congruent to  For example, the numbers congruent to  are



Mod 7, these are  Since we want  we choose 80.

For slightly larger numbers  and  making a list would be inefficient. However, the proof of the theorem gives a fast method for finding 

1. Use the Extended Euclidean algorithm to find  and  with 

2. Let 

# Example

Solve 

SOLUTION

First, we know from our calculations in Section 3.2 that



so  and  Therefore, 

How do you use the Chinese remainder theorem? The main idea is that if you start with a congruence mod a composite number  you can break it into simultaneous congruences mod each prime power factor of  then recombine the resulting information to obtain an answer mod  The advantage is that often it is easier to analyze congruences mod primes or mod prime powers than to work mod composite numbers.

Suppose you want to solve  Note that  We have



Now,  has two solutions:  Also,  has two solutions:  We can put these together in four ways:



So the solutions of  are 

In general, if  is the product of  distinct odd primes, then  has  solutions. This is a consequence of the following.

# Chinese Remainder Theorem (General Form)

Let  be integers with  whenever  Given integers   there exists exactly one solution  to the simultaneous congruences



For example, the theorem guarantees there is a solution to the simultaneous congruences



In fact,  is the answer.

Exercise 57 gives a method for computing the number  in the theorem.