
# 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.]