Next: Challenges! Up: Cryptology Class Notes Previous: Square roots

# Solving Congruences: The Chinese Remainder Theorem

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 congruences

have a unique solution x modulo mn.
Our example problem would have a unique solution modulo .

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 x=8.

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

mu+nv=1

Then all solutions are

One more example: and . First we have to solve

100u+49 v=1

Euclid's algorithm gives

Then . The solution is

Next: Challenges! Up: Cryptology Class Notes Previous: Square roots
David J. Wright
2000-09-11