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
$$\begin{align*}x&\equiv 13 \pmod {27}\\ x&\equiv 7 \pmod {16} \end{align*}$$
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
$$\begin{align*}x&\equiv a \pmod m\\ x&\equiv b \pmod n \end{align*}$$
have a unique solution x modulo mn.

Our example problem would have a unique solution modulo $16\cdot 27 = 432$.

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
$$\begin{align*}x&\equiv 2 \pmod{3}\\ x&\equiv 3 \pmod{5} \end{align*}$$
The numbers that satisfy the first congruence are in the sequence

$$2,\;5,\;8,\;11,\;14,\;17, ...$$

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 $ax\equiv b \pmod m$ 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.

$$\begin{array}{ccccccc\vert c\vert c} &&&&&&&0&1\\ \text{Di... ... 1 &5 & 3 \\ 5 &=& 5 &\cdot & 1 &+& 0 &27&16 \\ \end{array}$$

From the theory we discussed earlier, we know that $5\cdot 16 -3\cdot 27=-1$, or equivalently that $3\cdot 27 -5\cdot 16 =1$. This equation gives a very easy solution to our original simultaneous congruences:

$$x= (3\cdot27)\,7 -(5\cdot 16)\,13= -473.$$

Without working with -473, it is possible to quickly check that $-473 \equiv 13 \pmod {27}$ and $-473 \equiv 7 \pmod{16}$. The reason lies in the equation $3\cdot 27 -5\cdot 16 =1$. If we first interpret that equation mod 27, we see that $-5\cdot 16 \equiv 1 \pmod{27}$. Multiplying that congruence by 13 gives $-5\cdot 16 \cdot 13 \equiv 13 \pmod {27}$. Similarly, if we interpret things modulo 16, we find that $3\cdot27\cdot 7 \equiv 7 \pmod{16}$. 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 $-473+ k \, 432$ is a solution for any integer k. Often we add a multiple of 432 to make the solution positive: $-473+2\cdot 432 = 391$. We can check that $391\equiv 13 \pmod{27}$ and $391\equiv 7 \pmod{16}$.

Here is a summary of the whole process for
$$\begin{align*}x&\equiv a \pmod m\\ x&\equiv b \pmod n \end{align*}$$
First find integers u and v such that

mu+nv=1

Then all solutions are

$$x\equiv (mu)b +(nv)a \pmod{mn}$$

One more example: $x\equiv 23 \pmod {100}$ and $x\equiv 31\pmod {49}$. First we have to solve

100u+49 v=1

Euclid's algorithm gives

$$\begin{array}{ccccccc\vert c\vert c} &&&&&&&0&1\\ \text{Di... ...1 &49&24 \\ 2 &=& 2 &\cdot & 1 &+& 0 &100&49 \\ \end{array}$$

Then $49\cdot 49 -24\cdot 100 =1$. The solution is

$$49\cdot49\cdot 23 -24\cdot100\cdot 31 =-19177 \equiv 423 \pmod{4900}$$