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.
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
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.
(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
Use the Extended Euclidean algorithm to find and with
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.
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.