1.23: Chinese Remainder Theorem

The Chinese Remainder Theorem is an important theorem appearing for perhaps the first time in Sunzi Suanjing, a Chinese mathematical text written sometime during the 3rd to 5th centuries AD. We will illustrate its usefulness with an anecdote.

The child of a number theorist is sorting a large pile of pennies (worth less than a dollar) into groups of 3 pennies each. At the end, the child reports that 2 pennies are left over. The child starts over, instead sorting the pennies into groups of 4 and reports that 1 penny is left over. The child starts over again, sorting the pennies into groups of 11 and reports that 7 pennies are left over. The number theorist didn’t originally know how many pennies were in the pile, but at this point she speaks up.

What does she say? Did the child make a mistake in sorting the pennies? Or does the number theorist have enough information to tell how many pennies are in the pile?

We will answer this question with the Chinese Remainder Theorem. Here it is:

Theorem \(\PageIndex{1}\): Chinese Remainder Theorem

Let \(m_1,m_2,\dots,m_k\) be natural numbers such that each is greater than 1, and every pair of them is relatively prime. Let \(M = m_1m_2\cdots m_k\), and let \(b_1,b_2,\dots,b_k\) be integers. The system of congruences \[\begin{aligned} x &\equiv b_1 \pmod {m_1};\\ x &\equiv b_2 \pmod {m_2};\\ &\vdots\\ x &\equiv b_k \pmod {m_k};\\ \end{aligned}\] has a unique solution in the set \(\{0,1,2,\dots,M-1\}\).

Before we prove the theorem, let’s see what the number theorist from our story may have said.

Example \(\PageIndex{1}\): Chinese Remainder Theorem Pennies

Suppose that \(x\) is the number of pennies in the child’s pile. If we assume for a moment that the child didn’t make any mistakes in sorting the pennies into piles, then \(x\) satisfies the three congruences \[x \equiv 2 \pmod 3; \qquad x \equiv 1 \pmod 4; \qquad x \equiv 7 \pmod {11}.\nonumber \] At this point, since the moduli 3, 4, and 11 have the property that every two are relatively prime, the Chinese Remainder Theorem states that there is a unique solution to these congruences among the integers between 0 and 131 (here \(3\cdot 4 \cdot 11 = 132\)). In fact, we are told that there is a positive number of pennies, but there are fewer than one hundred, so exactly one number in \(\{1,2,\dots,99\}\) can be our solution to the number of pennies.

This is assuming that the child didn’t make any mistakes in counting, but the number theorist trusts her child (the child has been trained from the time he was in diapers to check his work), and the Chinese Remainder Theorem can’t point out any mistakes in the numbers on the right-hand sides of the congruences (the residues, not the moduli), since every choice of these numbers leads to a solution.

At this point the number theorist knows, at a minimum, that there is a unique solution to the system of congruences. However, if she was at this point able to tell her child how many pennies he has, we still don’t know what she said, because the Chinese Remainder Theorem alone does not tell us what the solution is—just that it exists. After we prove the Chinese Remainder Theorem, we will discuss a practical way of solving these systems of congruences, of finding the solution whose existence has been guaranteed.

Proof of Theorem \(\PageIndex{1}\)

Proof

We first prove that there exists a solution in \(\{0,\dots,M-1\}\); we will do this algorithmically.

Consider the first two congruences in the system: \[x \equiv b_1 \pmod {m_1}; \qquad x \equiv b_2 \pmod {m_2}.\nonumber \] Since \(m_1\) and \(m_2\) are relatively prime, Bezout’s Lemma (Lemma 1.9.1) implies that there exist integers \(s_1,t_1\) such that \[\label{eq: Bzt 1} s_1m_1+t_1m_2 = 1.\] We find these integers, perhaps using a technique from Section 1.10. Once we have, we construct a partial solution \(x_2\) by \[x_2 = b_1t_1m_2 + b_2s_1m_1.\nonumber \] Note here that we have attached the summands in equation \(\eqref{eq: Bzt 1}\) to the right-hand sides of the congruences, but in the “opposite” order. We use the subscript 2 and call \(x_2\) a partial solution because it satisfies the first two congruences we began with; \[\begin{aligned} x_2 &= b_1t_1m_2 + b_2s_1m_1\\ &\equiv b_1t_1m_2 \pmod {m_1}\\ &\equiv b_1(1-s_1m_1) \pmod {m_1}\\ &\equiv b_1 \pmod {m_1}, \end{aligned}\] and a similar argument shows that \(x_2 \equiv b_2 \pmod {m_2}\). Our next step is to record the information about our partial solution in its own congruence and pair it with the next unused congruence from our system: \[\begin{aligned} x &\equiv x_2 \pmod{m_1m_2};\\ x &\equiv b_3 \pmod{m_3}. \end{aligned}\] We solve this pair of congruences the same way we did the first pair; since \(m_1m_2\) and \(m_3\) can have no common prime factors, Bezout’s Lemma implies the existence of integers \(s_2,t_2\) such that \[s_2(m_1m_2) + t_2m_3 = 1,\nonumber \] and our next partial solution is \[x_3 = x_2t_2m_3 + b_3s_2(m_1m_2).\nonumber \] It’s possible to check that \(x_3\) satisfies the congruences modulo \(m_1\), \(m_2\), and \(m_3\). We once again move on to the next pair of congruences, using our partial solution and the next unused congruence: \[\begin{aligned} x &\equiv x_3 \pmod{m_1m_2m_3};\\ x &\equiv b_4 \pmod{m_4}. \end{aligned}\] We continue in this way until we reach the partial solution \(x_k\), which will be a solution to all \(k\) of the original \(k\) congruences. Thus the system has at least one solution.

We now must prove the uniqueness of the solution. Suppose that \(x\) and \(y\) both were congruent to \(b_1\) modulo \(m_1\), congruent to \(b_2\) modulo \(m_2\), and so on. Then \(x \equiv y \pmod {m_i}\) for each \(i\), meaning that each modulus \(m_i\) divides \(x-y\). Since every two of the moduli are relatively prime, this implies (see Exercise \(\PageIndex{1}\)) that \(m_1m_2\cdots m_k\) divides \(x-y\), which implies that \(x \equiv y \pmod M\). Thus there can only be one element of \(\{0,1,2,\dots,M-1\}\) that is a solution to the system of congruences.

The existence part of the proof of the Chinese Remainder Theorem gives us a way to construct solutions. Please carefully read the steps there. We illustrate the technique with a few examples.

Example \(\PageIndex{1}\): Continued

Resuming our earlier example, we solve the system of congruences \[x \equiv 2 \pmod 3; \qquad x \equiv 1 \pmod 4; \qquad x \equiv 7 \pmod {11}.\nonumber \] Beginning with the first two, we find coefficients for Bezout’s Lemma for the moduli 3 and 4, obtaining \(-1\cdot 3 + 1 \cdot 4 = 1\). We build our partial solution \[x_2 = 2\cdot 4 + 1 \cdot -3 = 5.\nonumber \] Thus \[x \equiv 5 \pmod {12} \qquad \text{and} \qquad x \equiv 7 \pmod{11}.\nonumber \] Now \(1 \cdot 12 - 1 \cdot 11 = 1\), so our next partial solution is \[x_3 = 5\cdot -11 + 7 \cdot 12 = 29.\nonumber \] Since we have used all of the original congruences, we conclude (and can check) that \(x=29\) is a solution to the system of congruences. The number theorist replies to her child that his pile has exactly 29 pennies.

Note that the uniqueness part of the Chinese Remainder Theorem only guarantees uniqueness of a solution among the residue classes modulo \(M\). For example, in our example it was necessary to know that there were fewer than 100 pennies, since \(x=161\) (\(=29+132\)), \(x=293\) (\(=29+2\cdot 132\)), and so on also satisfy all the congruences reported by the child. In general, a system of congruences satisfying the requirements of the Chinese Remainder Theorem is satisfied by an infinite number of integers \(x\), though only one of these belongs to the set \(\{0,1,\cdots,M-1\}\).

Example \(\PageIndex{2}\)

Let’s now describe all solutions to the system of congruences \[\begin{aligned} 2x &\equiv 5 \pmod 7;\\ 4x &\equiv 5 \pmod 9;\\ x &\equiv 4 \pmod {11};\\ x &\equiv 8 \pmod {13}. \end{aligned}\] This system is not yet ready for our technique from the previous example, since the first two congruences have extra coefficients on the left. We can address this problem by multiplying the first congruence by the inverse of 2 modulo 7 (which is 4) and multiplying the second congruence by the inverse of 4 modulo 9 (which is 7), obtaining \[\begin{aligned} x &\equiv 6 \pmod 7;\\ x &\equiv 8 \pmod 9;\\ x &\equiv 4 \pmod {11};\\ x &\equiv 8 \pmod {13}. \end{aligned}\] We begin now with the first two congruences. Since \(4\cdot 7 - 3\cdot 9 = 1\), our first partial solution is \(x_2 = 6\cdot -27 + 8\cdot 28 = 62\).

Working now with \(x \equiv 62 \pmod {63}\) and \(x \equiv 4 \pmod {11}\), using Blankinship’s Method or the Extended Euclidean Algorithm yields \(-4 \cdot 63 + 23 \cdot 11 = 1\). Our next partial solution is \(x_3 = 62\cdot 253 + 4 \cdot -252 = 14678\). This should make each of the first three congruences true, but it’s a rather large number; does it have to be this large?

Notice that \(7\cdot 9 \cdot 11 = 693\), and division yields \(14678 = 21 \cdot 693 + 125\). Let \(x_3' = 125\). Let’s look at the congruences \(x_3\) satisfies with \(x_3'\) in place of \(x_3\):

\(21 \cdot 693 + 125\)	\(\equiv\)	\(6\)	\(\pmod {7}\);		\(125\)	\(\equiv\)	\(6\)	\(\pmod {7}\);
\(21 \cdot 693 + 125\)	\(\equiv\)	\(8\)	\(\pmod {9}\);		\(125\)	\(\equiv\)	\(8\)	\(\pmod {9}\);
\(21 \cdot 693 + 125\)	\(\equiv\)	\(4\)	\(\pmod{11}\);		\(125\)	\(\equiv\)	\(4\)	\(\pmod{11}\).

Since \(693\) is divisible by each of \(7, 9, 11\), our partial solution \(x_3=14678\) has the same residues modulo these numbers as does \(x'_3=125\), so henceforth let’s replace \(14678\) by \(125\).

Moving on, the last pair of congruences we consider are \(x \equiv 125 \pmod {693}\) and \(x\equiv 8 \pmod {13}\). A little computation yields \(-3\cdot 693 + 160\cdot 13\), so \(x_4 = 125\cdot 2080 + 8\cdot -2079 = 243368\). Since \(7 \cdot 9 \cdot 11 \cdot 13 = 9009\), we can replace this number by \(x'_4 = 243368\bmod 9009 = 125\).

This last partial solution satisfies all four of our starting congruences, and by the Chinese Remainder Theorem, 125 is the only number in \(\{0,1,\dots,9008\}\) to do so. However, the question here is to determine all integer solutions to the congruences. These are precisely the integers \(x\) for which \(x \equiv 125 \pmod {9009}\), so the set of all solutions is precisely the set \[\left\{125 + 9009n \mid n \in \mathbb{Z}\right\}.\nonumber \]

We can now give a proof of the statement from the previous chapter that if \(a\) and \(b\) are relatively prime positive integers, then \(\phi(ab) = \phi(a)\phi(b)\).

Proof of Theorem 1.15.4

Consider the map \(f\) from \(U_{ab}\) defined by \[f([x]) = ([x]_a,[x]_b),\nonumber \] where \([x]_a\) and \([x]_b\) in the ordered pair indicate the residue classes containing \(x\) in \(U_a\) and in \(U_b\), respectively. Observe that each image under \(f\) is an ordered pair where the first entry is a residue class from \(U_a\) (of which there are \(\phi(a)\) possibilities) and the second entry is a residue class from \(U(b)\) (of which there are exactly \(\phi(b)\) possibilities). Thus there are \(\phi(a)\phi(b)\) possible ordered pairs that could appear as the outcomes of the mapping \(f\). Now we may apply the Chinese Remainder Theorem, since \(a\) and \(b\) are relatively prime. For every ordered pair \(([c],[d])\) there exists a unique solution \(x\) modulo \(ab\) to the congruences \(x \equiv c \pmod a\) and \(x \equiv d \pmod b\). Then by our definition of \(f\) we conclude that \(f([x]) = ([c],[d])\), and \([x]\) is the only element of \(U_{ab}\) that gets sent to \(([c],[d])\). This is true no matter what \(([c],[d])\) is, so there are exactly as many elements in \(U_{ab}\) as there are distinct ordered pairs \(([c],[d])\); thus \(\phi(ab)=\phi(a)\phi(b)\).

Before ending the chapter we mention that the Chinese Remainder Theorem is true in a more general context than that of the integers. For a certain broader class of rings\(^{1}\) (see Appendix C), if we use analogous notions of congruence and relative primeness, the Chinese Remainder Theorem still holds true. In particular, the Theorem is true for the Gaussian integers (see Exercise \(\PageIndex{6}\).

Exercises

Exercise \(\PageIndex{1}\)

Prove the following: if \(n\) and \(m_1,m_2,\cdots, m_n\) and \(N\) are all integers, and every two of \(m_1,m_2,\cdots,m_n\) are relatively prime, and \(m_1,m_2,\cdots,m_n\) each divide \(N\), then \(m_1m_2\cdots m_n\) divides \(N\).

(Hint: there are multiple proofs that can be given, using the prime factorization or Bezout’s Lemma and induction.)

Exercise \(\PageIndex{2}\)

Describe all solutions to the following systems of congruences.

1. \(x \equiv 1 \pmod {8}\); \(x \equiv 2 \pmod 9\).
2. \(3x \equiv 8 \pmod {10}\); \(x \equiv 13 \pmod {21}\).

Exercise \(\PageIndex{3}\)

Solve this problem attributed to Euler: Find two numbers whose sum is 100 such that one is divisible by seven and the other is divisible by 11.

Exercise \(\PageIndex{4}\)

Give all solutions to the system of congruences: \[x \equiv 2 \pmod 3; \qquad x \equiv 2 \pmod 5; \qquad x \equiv 5 \pmod 7.\nonumber \]

Exercise \(\PageIndex{5}\)

1. Explain why the system of congruences \[x \equiv 3 \pmod 6; \qquad x \equiv 4 \pmod 8\nonumber \] has no solution. Explain why this does not violate the Chinese Remainder Theorem.
2. Find all numbers in \(\{0,1,2,\dots,100\}\) that are solutions to the system of congruences \[x \equiv 2 \pmod 6; \qquad x \equiv 4 \pmod 8.\nonumber \] Can you describe (and justify) what the set of all integer solutions to this system of congruences is?
3. Can you describe a moral to this story? To you, what does this exercise illustrate about systems of congruences and the Chinese Remainder Theorem?

Exercise \(\PageIndex{6}\)

Use ideas from this chapter and from Section 1.13 (including the exercises) to solve the following systems of congruences. Your answers should be Gaussian integers.

1. \(x \equiv i \pmod{1+i}\); \(x \equiv 2 \pmod {3i}\).
2. \(x \equiv -3+i \pmod 5\); \(x \equiv -i \pmod {1-i}\).

Footnotes

[1] Namely, the principal ideal domains.