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:

Our example problem would have a unique solution modulo .Chinese Remainder Theorem:For relatively prime modulimandn, the congruences

have a unique solutionxmodulomn.

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

Just scan this sequence for a term that also leaves remainder 3 after division by 5. The answer is

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.

From the theory we discussed earlier, we know that , or equivalently that . This equation gives a very easy solution to our original simultaneous congruences:

Without working with -473, it is possible to quickly check that and . The reason lies in the equation . If we first interpret that equation mod 27, we see that . Multiplying that congruence by 13 gives . Similarly, if we interpret things modulo 16, we find that . That verifies our solution for the Chinese Reminder problem.

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

Then all solutions are

One more example:
and
.
First we have to solve

100*u*+49 *v*=1

Euclid's algorithm gives

Then . The solution is