2.3: The Chinese Remainder Theorem

\(\newcommand{\NN}{\mathbb N}\)
\(\newcommand{\RR}{\mathbb R}\)
\(\newcommand{\QQ}{\mathbb Q}\)
\(\newcommand{\ZZ}{\mathbb Z}\)
\(\newcommand{\Cc}{\mathcal C}\)
\(\newcommand{\Dd}{\mathcal D}\)
\(\newcommand{\Ee}{\mathcal E}\)
\(\newcommand{\Ff}{\mathcal F}\)
\(\newcommand{\Kk}{\mathcal K}\)
\(\newcommand{\Mm}{\mathcal M}\)
\(\newcommand{\Pp}{\mathcal P}\)
\(\newcommand{\ind}{\operatorname{ind}}\)
\(\newcommand{\ord}{\operatorname{ord}}\)

In this section, we discuss solutions of systems of congruences having different moduli. An example of this kind of systems is the following: find a number that leaves a remainder of \(1\) when divided by \(2\), a remainder of \(2\) when divided by three, and a remainder of \(3\) when divided by \(5\). We shall see that there is a systematic way of solving this kind of system.

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

Fix a \(k\in\NN\). Then given \(b_1,\dots,b_k\in\ZZ\) and \(n_1,\dots,n_k\in\NN\), the system of congruences \[\begin{aligned} x&\equiv b_1\pmod{n_1}\\ x&\equiv b_2\pmod{n_2}\\ &\vdots\\ x&\equiv b_k\pmod{n_k}\end{aligned}\] has a solution \(x\in\ZZ\) if the \(n_1,n_2,\dots,n_k\) are pairwise relatively prime. The solution is unique modulo \(N=n_1\,n_2\dots n_k\).

Proof

For \(j=1,\dots,k\), let \(N_j=N/n_j\). Since the moduli \(n_j\) are pairwise relatively prime, \(\gcd(N_j,n_j)=1\) – after all, \(N_j\) is the product of all the moduli except \(n_j\). Hence by Corollary 2.2.1, \(\exists y_j = N_j^{-1}\) modulo \(n_j\), satisfying \(N_jy_j\equiv 1\pmod{n_j}\). Consider now \[x=\sum_{j=1}^k b_j N_j y_j\] Since \[N_j\equiv 0\pmod{n_i} \ \ \forall i\neq j,\] we see that \[x\equiv b_j N_j y_j\equiv b_j\pmod{n_j}.\] Hence \(x\) is a solution to the system of congruences.

We have to show now that any two solutions are congruent modulo \(N\). Suppose that \(x\) and \(y\) are both solutions of the system of congruences. Then \(x\equiv b_j\equiv y\pmod{n_j}\), or \(n_j\mid x-y\), for all \(1\leq j\leq k\). But then, since the moduli are pairwise relatively prime, using Theorem 2.1.2 \(k\) times (formally, this needs to be done by induction!), we can conclude that \(N=n_1\dots n_k\mid x-y\) or \(x\equiv y\pmod N\).

Example \(\PageIndex{1}\)

Solve the system \[\begin{aligned} x&\equiv 1\pmod2\\ x&\equiv 2\pmod3\\ x&\equiv 3\pmod5.\end{aligned}\] We have \(N=2\cdot3\cdot5=30\). Also \[N_1= \dfrac{30}{2} =15,\ N_2= \dfrac{30}{3}=10,\ \mbox{and} \ N_3= \dfrac{30}{5}=6.\] So we have to solve now \(15y_1\equiv 1\pmod2\) – a solution is \(y_1\equiv 1\pmod2\). In the same way, we find that \(y_2\equiv 1\pmod3\) and \(y_3\equiv 1\pmod5\). Therefore \[x=1\cdot15\cdot1+2\cdot10\cdot1+3\cdot6\cdot1=53\equiv 23\pmod{30}.\]

Exercise \(\PageIndex{1}\)

1. Find an integer that leaves a remainder of \(2\) when divided by either \(3\) or \(5\), but that is divisible by \(4\).
2. Find all integers that leave a remainder of \(4\) when divided by \(11\) and leaves a remainder of \(3\) when divided by \(17\).
3. Find all integers that leave a remainder of \(1\) when divided by \(2\), a remainder of \(2\) when divided by \(3\), and a remainder of \(3\) when divided by \(5\).
4. A band of \(17\) pirates steal some gold bars. When they try to divide the spoils equally, \(3\) bars are left over – so a fight breaks out, killing one. This immediately brings calm as they see if the gold can now be evenly shared. Unfortunately, there are now \(10\) bars left out, so they fight again. After the inevitable (single) further death, a perfect division is now possible. What is the minimum number of gold bars the pirates could have started with? [This is apparently an ancient Chinese problem.]