Skip to main content

# 3.4: The Chinese Remainder Theorem

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

In this section, we discuss the solution of a system 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. This kind of question can be translated into the language of congruences. As a result, in this chapter, we present a systematic way of solving this system of congruences.

The system of congruences

\begin{aligned} && x\equiv b_1(mod \ n_1),\\&&x\equiv b_2(mod \ n_2),\\&&.\\&&.\\&&.\\&& x\equiv b_t(mod \ n_t),\end{aligned}

has a unique solution modulo $$N=n_1n_2...n_t$$ if $$n_1,n_2,...,n_t$$ are pairwise relatively prime positive integers.

Let $$N_k=N/n_k$$. Since $$(n_i,n_j)=1$$ for all $$i\neq j$$, then $$(N_k,n_k)=1$$. Hence by Theorem 26 , we can find an inverse $$y_k$$ of $$N_k$$ modulo $$n_k$$ such that $$N_ky_k\equiv 1(mod \ n_k)$$. Consider now

$x=\sum_{i=1}^tb_iN_iy_i$

Since $N_j\equiv 0(mod \ n_k) \ \ \mbox{for all} \ \ j\neq k,$ thus we see that $x\equiv b_kN_ky_k(mod \ n_k).$ Also notice that $$N_ky_k\equiv 1(mod \ n_k)$$. Hence $$x$$ is a solution to the system of t congruences. We have to show now that any two solutions are congruent modulo $$N$$. Suppose now that you have two solutions $$x_0,x_1$$ to the system of congruences. Then $x_0\equiv x_1(mod \ n_k)$ for all $$1\leq k\leq t$$. Thus by Theorem 23, we see that $x_0\equiv x_1(mod \ N).$ Thus the solution of the system is unique modulo $$N$$.

We now present an example that will show how the Chinese remainder theorem is used to determine the solution of a given system of congruences.

Example $$\PageIndex{1}$$:

Solve the system \begin{aligned} && x\equiv 1(mod \ 2)\\&& x\equiv 2(mod \ 3)\\&& x\equiv 3(mod \ 5).\end{aligned} We have $$N=2.3.5=30$$. Also $N_1=30/2=15, N_2=30/3=10 \mbox{and} \ \ N_3=30/5=6.$ So we have to solve now $$15y_1\equiv 1(mod \ 2)$$. Thus $y_1\equiv 1(mod \ 2).$ In the same way, we find that $y_2\equiv 1(mod \ 3) \mbox{and} \ \ y_3\equiv 1(mod \ 5).$ As a result, we get $x\equiv 1.15.1+2.10.1+3.6.1\equiv 53\equiv 23 (mod \ 30).$

Exercises

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.

### Contributors

• Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.