In considering the problem of finding modular square roots, we found that the problem for a general modulus m could be reduced to that for a prime power modulus. The next problem would be how to piece the solutions for prime powers together to solve the original congruence. This is done by the Chinese Remainder Theorem, so-called because it appeared in ancient Chinese manuscripts.
A typical problem is to find integers x that simultaneously solve
It's important in our applications that the two moduli be relatively prime; otherwise, we would have to check that the two congruences are consistent. The Chinese Remainder Theorem has a very simple answer:
Chinese Remainder Theorem: For relatively prime moduli m and n, the congruencesOur example problem would have a unique solution modulo .
have a unique solution x modulo mn.
It's better than this; there is a relatively simple algorithm to find the solution. Since all number theory algorithms ultimately come down to Euclid's algorithm, you can be sure it happens here as well.
First let's consider an even simpler example. Suppose we want all
numbers x that satisfy
The numbers that satisfy the first congruence are in the sequence
Euclid's algorithm (see Section 4) can be used to solve
several problems: finding the greatest common divisor d of two numbers
m and n, and finding two numbers x and y such that mx+ny=d,
and solving congruences
for x. We will now see
how it also helps to solve Chinese Remainder problems. We will start
with m=27 and n=16. Here is what Euclid's algorithm gives.
The number x=-473 is not the only solution; if we modify it by a multiple of both 27 and 16, we won't change the congruences. That means is a solution for any integer k. Often we add a multiple of 432 to make the solution positive: . We can check that and .
Here is a summary of the whole process for
First find integers u and v such that
One more example:
First we have to solve