Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

3.4: The Chinese Remainder Theorem

  • Page ID
    8834
  • [ "article:topic", "Chinese Remainder Theorem", "authorname:wraji" ]

    \( \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.