The Chinese Remainder Theorem

Section 4.5 The Chinese Remainder Theorem

Objectives

State the Chinese Remainder Theorem and use it to solve systems of congruences and related problems.

The Chinese Remainder Theorem is a result in number theory about solving simultaneous systems of several linear congruences. In this section we explore its origins and give methods to solve these systems.

Exploration 4.5.1. Sun Zi's Problem.

Sun Zi (孙子) was a Chinese mathematician who in his text Sunzi Suanjing《孙子算经》 (3rd to 5th century AD) is said to have written the earliest known reference to systems of linear congruences. In it he writes:

‘今有物，不知其数。三、三数之，剩二；五、五数之，剩三；七、七数之，剩二。问物几何？’
―孙子。《孙子算经》。

‘A number is repeatedly divided by 3, the remainder is 2; divided by 5, the remainder is 3; and by 7, the remainder is 2. What will the number be?’
―Sun Zi, Sunzi Suanjing, Vol. 3, Problem 26 (as cited in [5])

We follow Sun Zi's method of solving this system.

(a)

The first condition in Sun Zi's problem can be written as

\begin{equation*} x \equiv 2 \Mod{3}\text{.} \end{equation*}

Write all three conditions as a system of linear congruences.

(b)

Since the integers 3, 5, and 7 are pairwise relatively prime, then \(35^{-1} \Mod{3}\) exists. Compute this quantity.

Similarly, compute \(21^{-1} \Mod{5}\) and \(15^{-1} \Mod{7}\text{.}\)

(c)

Explain why each of the following congruences hold:

\begin{equation*} \begin{cases} 2 \cdot 35^{-1} \cdot 35 \equiv 2 \Mod{3} \\ 3 \cdot 21^{-1} \cdot 21 \equiv 3 \Mod{5} \\ 2 \cdot 15^{-1} \cdot 15 \equiv 2 \Mod{7} \end{cases}\text{.} \end{equation*}

(d)

Explain why we can conclude that

\begin{equation*} x \equiv 2 \cdot 35^{-1} \cdot 35 + 3 \cdot 21^{-1} \cdot 21 + 2 \cdot 15^{-1} \cdot 15 \Mod{105} \end{equation*}

is a solution to the original system of congruences, and using your answers from (b) simplify this expression to get an answer modulo 105.

Finally, verify that the answer satisfies all three conditions.

The method outlined in Exploration 4.5.1 actually works for the general case, as long as the moduli in the system are pairwise relatively prime. Before stating our main theorems let's look at a smaller examples, one with only two congruences.

Checkpoint 4.5.1. Two Congruences.

Find a natural number \(x\) that leaves a remainder of 3 when divided by 5, and a remainder of 1 when divided by 7.

Hint

What are the numbers that satisfy the first condition? Among these, find one satisfying the second as well.

The solution to Checkpoint 4.5.1 did not use the same method as Exploration 4.5.1 and instead just relied on listing numbers. This won't be efficient for larger systems, so let's try to proceed more systematically.

Theorem 4.5.2. Solution to a system of two congruences.

Let \(m_1,m_2 \in \mathbb{N}\) and \(\gcd(m_1,m_2) = 1\text{,}\) and consider the system

\begin{equation*} \begin{cases} x \equiv a \Mod{m_1} \\ x \equiv b \Mod{m_2} \end{cases}\text{.} \end{equation*}

Perform the following steps:

Find the multiplicative inverse of \(m_2\) modulo \(m_1\text{,}\) call it \(t\text{.}\)
Find the multiplicative inverse of \(m_1\) modulo \(m_2\text{,}\) call it \(s\text{.}\)

A solution to the given system is

\begin{equation*} x \equiv atm_2 + bsm_1 \Mod{m_1m_2}\text{,} \end{equation*}

and this is unique modulo \(M = m_1m_2\text{.}\)

Checkpoint 4.5.3. Two Congruences, again.

Solve Checkpoint 4.5.1 by writing its two conditions as a system of two congruences and apply the method in Theorem 4.5.2.

Theorem 4.5.2 speaks to the existence and uniqueness of a solution to the given system. Try proving it yourself in the next two exercises!

Checkpoint 4.5.4. Theorem 4.5.2, existence.

Prove that \(x \equiv atm_2 + bsm_1 \Mod{m_1m_2}\) satisfies both congruences in the given system.

Checkpoint 4.5.5. Theorem 4.5.2, uniqueness.

Prove that \(x \equiv atm_2 + bsm_1 \Mod{m_1m_2}\) is the only solution to the given system modulo \(m_1m_2\text{.}\)

Finally we state a method for a general system of congruences.

Theorem 4.5.6. Solution to a general system of congruences.

Let \(m_1,m_2,\ldots,m_n \in \mathbb{N}\) and \(\gcd(m_i,m_j) = 1\) for \(i \ne j\text{,}\) and consider the system

\begin{equation*} \begin{cases} x \equiv a_1 \Mod{m_1} \\ x \equiv a_2 \Mod{m_2} \\ \vdots \\ x \equiv a_n \Mod{m_n} \end{cases} \end{equation*}

Perform the following steps:

Let \(M = m_1m_2\cdots m_n\text{.}\)
For each \(i = 1,2,\ldots,n\text{:}\)
- Define \(b_i = M/m_i\) (the product of all moduli other than \(m_i\)).
- Find the multiplicative inverse of \(b_i\) modulo \(m_i\text{,}\) call it \(t_i\text{.}\)

A solution to the given system is

\begin{equation*} x \equiv a_1b_1t_1 + a_2b_2t_2 + \cdots + a_nb_nt_n \Mod{M}\equiv \sum_{i=1}^n a_ib_it_i \Mod{M}\text{,} \end{equation*}

and this is unique modulo \(M\text{.}\)

Checkpoint 4.5.7. Sun Zi's System.

Verify that the method outlined in Theorem 4.5.6 produces the same steps and answer as in Exploration 4.5.1.

Checkpoint 4.5.8. Practice.

Solve the system of congruences

\begin{equation*} \begin{cases} x \equiv 4 \Mod{5} \\ x \equiv 5 \Mod{6} \\ x \equiv 6 \Mod{7} \end{cases} \end{equation*}

using the method in Theorem 4.5.6.

One consequence of Theorem 4.5.6 is that there is a bijection between n-tuples

\begin{equation*} (a_1,a_2,\ldots,a_n) \in \mathbb{Z}_{m_1} \times \mathbb{Z}_{m_2} \times \cdots \times \mathbb{Z}_{m_n} \end{equation*}

and congruence classes modulo \(M = \prod_{i=1}^n m_i\text{,}\) as long as the moduli \(m_i\) are pairwise relatively prime.

That is, any number in \(\{0,1,\ldots,M\}\) has a unique representation as a collection of remainders \(a_i\) for each modulus \(m_i\text{.}\)

Example 4.5.9. From \(\mathbb{Z}_{10}\) to \(\mathbb{Z}_2 \times \mathbb{Z}_5\).

Let \(x \equiv 1 \Mod{2}\) and \(x \equiv 2 \Mod{5}\text{.}\) Then Theorem 4.5.6 tells us that the solution \(x \equiv 7 \Mod{10}\) is unique.

In fact for any pair of remainders modulo 2 and 5, we get a unique congruence class modulo 10 as a solution to the system

\begin{equation*} \begin{cases} x \equiv a_1 \Mod{2} \\ x \equiv a_2 \Mod{5}\end{cases} \end{equation*}

Verify that we have a bijection between \(\mathbb{Z}_2 \times \mathbb{Z}_5\) and \(\mathbb{Z}_{10}\text{:}\)

\(\mathbb{Z}_2 \times \mathbb{Z}_5\)	\(\mathbb{Z}_{10}\)
\((0,0)\)	\(0\)
\((0,1)\)	\(6\)
\((0,2)\)	\(2\)
\((0,3)\)	\(8\)
\((0,4)\)	\(4\)

\(\mathbb{Z}_2 \times \mathbb{Z}_5\)	\(\mathbb{Z}_{10}\)
\((1,0)\)	\(5\)
\((1,1)\)	\(1\)
\((1,2)\)	\(7\)
\((1,3)\)	\(3\)
\((1,4)\)	\(9\)

Checkpoint 4.5.10. Computing large powers.

Verify that 19 is a solution to the system

\begin{equation*} \begin{cases} x \equiv 1 \Mod{3} \\ x \equiv 5 \Mod{7}\end{cases} \end{equation*}

Then, use this fact to compute \(19^{20} \mmod{21}\text{.}\)

Hint

Instead of computing large powers of 19, compute large powers of 1 and 5 (with respective moduli) then use Theorem 4.5.2.

Solutions Solutions to Selected Checkpoints

Checkpoint 4.5.1. Two Congruences.

Solution