Chinese Remainder Theorem

Subsection 5.4.2 Chinese Remainder Theorem

Theorem 5.4.2.1. Chinese Remainder Theorem.

Let \(m = m_1 m_2 \cdots m_r\) with \(\gcd(m_i,m_j) = 1\) for all \(i \neq j\text{.}\) Then the system

\begin{equation*} \left\{ {\begin{array}{l} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod{m_2}\\ \quad \vdots\\ x \equiv a_r \pmod{m_r}\\ \end{array}} \right\} \end{equation*}

has a unique solution modulo \(m\text{,}\) given by

\begin{equation*} x =a_1e_1 + a_2 e_2+\cdots +a_r e_r, \quad \text{where } e_i = w_i\cdot t_i, \end{equation*}

with

\begin{equation*} w_i=\frac{m}{m_i}\quad \text{and} \quad t_iw_i \equiv 1 \pmod{m_i}. \end{equation*}

In other words, the solution set is exactly the congruence class of \(x\) modulo \(m\text{,}\)

\begin{equation*} [x] = \set{x + km \mid k \in \ZZ}. \end{equation*}

🔗

Remark 5.4.2.2.

Roughly speaking, the \(e_i\) is \(1\) in the mod \(m_i\) direction and \(0\) in the mod \(m_j\) direction for \(i \neq j\text{.}\)

🔗

Steps to solve Chinese Remainder Theorem> 5.4.2.1 problem:

Identify \(a_i\) and \(m_i\text{.}\)
🔗

🔗
Compute \(m\) and \(w_i\text{.}\)
🔗

🔗
Compute \(t_i\text{,}\) the inverse of \(w_i\) modulo \(m_i\text{.}\)
🔗

🔗
There is a unique solution modulo \(m\)
🔗

🔗

🔗

Example 5.4.2.3. System of two congruences.

Use the Chinese Remainder Theorem> 5.4.2.1 to find all of the solutions to following the system of congruences.

\begin{equation*} \left\{ {\begin{array}{l} x \equiv 7 \pmod{12}\\ x \equiv 3 \pmod{5}\\ \end{array}} \right\} \end{equation*}

🔗

Solution.

Following the notation above, we have \(a_1 = 7\text{,}\) \(m_1 = 12\text{,}\) \(a_2 = 3\text{,}\) and \(m_2 = 5\text{.}\) Since \(\gcd(12,5) = 1\text{,}\) we can use Chinese Remainder Theorem> 5.4.2.1. We are guaranteed a unique solution modulo \(m = 12 \cdot 5 = 60\text{.}\) It has the form

\begin{equation*} x \equiv 7 \cdot e_1 + 3 e_2 \pmod{60}. \end{equation*}

Recall that \(e_1\) is an integer such that \(e_1 \equiv 1 \pmod{12}\) and \(e_1 = 0 \pmod{5}\text{.}\) We can compute \(e_1\) as \(e_1 = w_1 t_1\text{,}\) where \(w_1 = m/m_1\text{,}\) and \(t_1\) is the inverse of \(w_1\) modulo \(m_1\text{.}\) Then \(w_1 = 5\text{.}\) By inspection, we can take \(t_1 = 5\text{,}\) since \(5 \cdot w_1 \equiv 1 \pmod{12}\text{.}\) Then \(e_1 = 5 \cdot 5 = 25\text{.}\)

🔗

Similarly, \(e_2 = w_2 t_2\text{,}\) where \(w_2 = m/m_2 = 12\text{.}\) We compute the inverse of \(12\) modulo \(5\text{,}\) but this is the same as the inverse of \(2\) modulo \(5\text{,}\) since \(12 \equiv 2 \pmod{5}\text{.}\) By inspection, we can take \(t_2 = 3\text{,}\) so \(e_2 = 12 \cdot 3 = 36\text{.}\)

🔗

Then

\begin{equation*} x \equiv 7 \cdot 25 + 3 \cdot 36 \equiv 283 \equiv 43 \pmod{60}. \end{equation*}

Equivalently,

\begin{equation*} x = 43 + 60 k, \quad \text{ for }k \in \ZZ. \end{equation*}

🔗

Example 5.4.2.4. System of four congruences.

Find all the solutions to

\begin{equation*} \left\{ {\begin{array}{l} x \equiv 1 \pmod 2\\ x \equiv 2 \pmod 3\\ x \equiv 3 \pmod 5\\ x \equiv 4 \pmod{11}\\ \end{array}} \right\}. \end{equation*}

🔗

Solution.

Since \(2, 3, 5, 11\) are pairwise coprime, we can use Chinese Remainder Theorem> 5.4.2.1. There is a unique solution modulo \(m = 2 \cdot 3 \cdot 5 \cdot 11 = 330\text{.}\) Let \(w_i = \frac{m}{m_i}\text{.}\) Then

\begin{align*} w_1 \amp = 165 \\ w_2 \amp = 110 \\ w_3 \amp = 66 \\ w_4 \amp = 30. \end{align*}

We compute \(t_i\) such that \(t_iw_i \equiv 1 \pmod{m_i}\text{.}\) Then \(t_1\) is the inverse of \(165\) modulo \(2\text{.}\) We take \(t_1 = 1\text{.}\) Similarly, \(t_2\) is inverse of \(110\) modulo \(3\text{,}\) which is the same as the inverse of \(2\) modulo \(3\text{.}\) We pick \(t_2 = 2\text{.}\) Similarly, we can take \(t_3 = 1\) and \(t_4 = 7\text{.}\) Then

\begin{align*} e_1 \amp = t_1 w_1 = 1 \cdot 165 = 165 \\ e_2 \amp = t_2 w_2 = 2 \cdot 110 = 220 \\ e_3 \amp = t_3 w_3 = 1 \cdot 66 = 66 \\ e_4 \amp = t_4 w_4 = 7 \cdot 30 = 210. \end{align*}

Then

\begin{align*} x \amp \equiv 1 \cdot e_1 + 2 e_2 + 3 e_3 + 4 e_4 \pmod{330} \\ \amp \equiv 1 \cdot 165 + 2 \cdot 220 + 3 \cdot 66 + 4 \cdot 210 \end{align*}

Thus \(x = 323 + 330k\text{,}\) for \(k \in \ZZ\text{.}\) Equivalently, \(x \equiv 323 \pmod{330}\text{.}\)

🔗

Example 5.4.2.5. Action figures.

My son had \(500\) action figures before we moved to Greensboro. He has not bought any new ones, but he lost a few in the process of the move, and he wants to know how many he has now. He can only count accurately to \(10\text{,}\) but he knows that you are a number theorist, and he has faith in you. He reports that there is an odd number left. When you tell him that is not enough information, he reports that there is \(1\) left over if he lines them up \(5\) at a time, \(2\) left over if he lines the up \(7\) at a time, and \(3\) left over if he lines them up \(9\) at a time. How many action figures does he have?

🔗

Solution.

Let \(x\) be the number of action figures my son has. Then

\begin{align*} x\amp\equiv 1 \pmod{2} \amp \text{since }x\text{ is odd} \\ x \equiv 1 \pmod{5} \amp \text{since there is }1\text{ left over in rows of }5 \\ x \equiv 2 \pmod{7} \amp \text{since there is }2\text{ left over in rows of }7 \\ x \equiv 3 \pmod{9} \amp \text{since there is }3\text{ left over in rows of }9 \end{align*}

Note that we can solve for \(x\) using Chinese Remainder Theorem> 5.4.2.1 since

\begin{equation*} \gcd(2,5) = \gcd(2,7) = \gcd(2,9) = \gcd(5,7) = \gcd(5,9) = \gcd(7,9) = 1. \end{equation*}

🔗

Let’s follow the steps to solve a Chinese Remainder Theorem> 5.4.2.1 problem:

We identify \(a_i\) and \(m_i\text{.}\) We have
🔗

🔗
We compute
🔗

🔗
🔗

🔗
We compute
🔗

🔗

In other words, \(x = 471 + 630k\) for some integer \(k\text{.}\) Since my son has less than \(500\) action figures, he must have \(471\) action figures.

🔗

Prev Top Next