Skip to main content

Section 4.2 Chinese Remainder Theorem

number

Now we add yet another twist to solving congruences.

In the first century A.D. Sun-Tsu asked what number yields remainders of \(2,3,\) and \(2\) when divided by \(3,5,\) and \(7,\) respectively? This is equivalent to solving the system

\begin{align*} x \amp \equiv 2\pmod{3}\\ x \amp \equiv 3\pmod{5}\\ x \amp \equiv 2\pmod{7} \end{align*}

Let \(n = n_1n_2...n_r,\) and for each \(k = 1, 2,..., r\) let

\begin{equation*} N_k=\frac{n}{n_k}. \end{equation*}

Note that this gives \(\gcd(N_k, n_k) = 1.\) So the congruence \(N_kx \equiv 1\pmod{n_k}\) has a unique solution modulo \(n_k,\) say \(x_k.\) We will show that the integer

\begin{equation*} \overline{x} = a_1N_1x_1 + a_2N_2x_2 +...+ a_rN_rx_r \end{equation*}

is a simultaneous solution to the given system.

Since \(n_i\vert N_k\) for \(i \neq k, N_i \equiv 0 \pmod{n_k}\) if \(i\neq k.\) Thus

\begin{equation*} \overline{x} = a_1N_1x_1 + a_2N_2x_2 +...+ a_rN_rx_r \equiv a_kN_kx_k\pmod{n_k}. \end{equation*}

But since \(N_kx_k \equiv 1 \pmod{n_k},\) we have that

\begin{equation*} \overline{x} \equiv a_k\cdot 1 \equiv a_k\pmod{n_k}. \end{equation*}

Thus \(\overline{x}\) is a simultaneous solution.

To see that it is unique modulo \(n,\) suppose that \(\overline{x}'\) is any other solution that satisfies the given system. Then

\begin{equation*} \overline{x} \equiv a_k \equiv \overline{x}'\pmod{n_k} \end{equation*}

and so \(n_k\vert (\overline{x}-\overline{x}')\) for each \(k.\) But since \(\gcd(n_i, n_j)=1\) for \(i\neq j,\) we have that \(n_1n_2...n_r = n\vert (\overline{x}-\overline{x}').\) Thus \(\overline{x}\equiv\overline{x}'\pmod{n}.\) This proves the theorem.

To solve Sun-Tsu's problem, we have

\begin{align*} x \amp \equiv 2\pmod{3}\\ x \amp \equiv 3\pmod{5}\\ x \amp \equiv 2\pmod{7} \end{align*}

Using the notation of the Chinese Remainder Theorem, we have \(n = 3\cdot 5\cdot 7 =105\) and

\begin{equation*} N_1=\frac{n}{3}=35 \hspace{10mm} N_2=\frac{n}{5}=21 \hspace{10mm} N_3=\frac{n}{7}=15. \end{equation*}

To find the \(x_i\)'s we solve each of the congruences

\begin{align*} x \amp \equiv 35x \pmod{3}\\ x \amp \equiv 21x \pmod{5}\\ x \amp \equiv 15x \pmod{7} \end{align*}

so that we have \(x_1 = 2, x_2 = 1, x_3 = 1.\) So a solution of the given system is

\begin{equation*} x = 2\cdot 35\cdot 2 + 3\cdot 21\cdot 1 + 2\cdot 15\cdot 1 = 233 \equiv 23\pmod{105}. \end{equation*}

Now we can finally solve some more general congruences. Consider the next example. As a different way to solve some congruences.

Using the Chinese Remainder Theorem we can solve the congruence

\begin{equation*} 17x \equiv 9 \pmod{276}. \end{equation*}

Since \(276 = 3\cdot 4\cdot 23,\) we turn our one congruence into the system

\begin{align*} 17x \amp \equiv 9 \pmod{3}\\ 17x \amp \equiv 9 \pmod{4}\\ 17x \amp \equiv 9 \pmod{23} \end{align*}

which reduced is

\begin{align*} x \amp \equiv 0 \pmod{3}\\ x \amp \equiv 1 \pmod{4}\\ 17x \amp \equiv 9 \pmod{23} \end{align*}

Since \(x\equiv 0 \pmod{3}\) we know that \(x = 3k\) for some \(k.\) So we substitute this in the next congruence to see that

\begin{equation*} 3k \equiv 1\pmod{4} \end{equation*}

and so

\begin{equation*} k \equiv 3\pmod{4}, \end{equation*}

so that \(k = 3 + 4j\) for some \(j,\) so that \(x = 3(3 + 4j) = 9 + 12j.\) Now we substitute this into the last congruence so that we need only solve

\begin{equation*} 17(9 + 12j) \equiv 9 \pmod{23}. \end{equation*}

This reduces to

\begin{align*} 17(9 + 12j) \amp \equiv 9 \pmod{23}\\ 153+204j \amp \equiv 9 \pmod{23}\\ 15+20j \amp \equiv 9 \pmod{23}\\ 20j \amp \equiv 17 \pmod{23} \end{align*}

so that \(j \equiv 2 \pmod{23}.\) So \(j = 2 + 23t\) for \(t \in\mathbb{Z}.\) Hence

\begin{equation*} x = 9 + 12(2 + 23t) = 33 + 276t, \end{equation*}

so \(x \equiv 33 \pmod{276}\) is the unique solution modulo \(276.\) It is unique since \(\gcd(17, 276) = 1.\)

The Chinese Remainder Theorem has numerous applications. It is conceivable that one of these might have been how the Chinese generals counted their troops:

\(\hspace{10mm}\) Line up \(7\) by \(7\text{!}\) \(\hspace{5mm}\) (Not factorial, but a SCREAMED military command.)

\(\hspace{10mm}\) Line up \(11\) by \(11\text{!}\)

\(\hspace{10mm}\) Line up \(13\) by \(13\text{!}\)

\(\hspace{10mm}\) Line up \(17\) by \(17\text{!}\)

Counting only the remainders in the incomplete rows, the intelligent generals could know the exact number of their soldiers 1 .

In between us, this may never have been practiced. The existence of intelligent generals remains a wide open question.