What is the Chinese remainder theorem?

The Chinese remainder theorem (CRT) is foundational in number theory and modular arithmetic, enabling the resolution of a set of concurrent congruence equations that delineate remainders from division operations. The CRT stands as a crucial concept with diverse practical implications and is widely applicable across multiple domains such as number theory, cryptography, and error-correcting codes. In this Answer, we will explore the Chinese remainder theorem, understand its basic principles, and see how it can be applied to solve problems.

Before diving into the details, it is helpful to have a basic understanding of modular arithmetic and some familiarity with mathematical notation.

Mathematical representation

The Chinese remainder theorem is a number theory principle that governs resolving a set of concurrent linear congruences. A linear congruence is a type of equation that has the following form:

Where:

  • cc, rr, and mm are integers.

  • cc is called the coefficient.

  • rr is the remainder.

  • mm is the modulus.

For a system of such congruences, the CRT offers a method of solving it if the moduli are pairwise coprime, meaning their greatest common divisors are 11. In simpler terms, the moduli have only one common factor: 11

Formula principles

The CRT is based on the following principles:

  1. Existence of a solution: Given a system of congruences with pairwise coprime moduli, a unique solution exists modulo the product of all the moduli.

  2. Chinese remainder theorem formula: The unique solution can be determined using the following formula:

Where:

  • xx is the unique solution.

  • r₁,r₂,...,rkr₁, r₂, ..., rk are the remainders in the system of congruences.

  • m₁,m₂,...,mkm₁, m₂, ..., mk are the moduli in the system of congruences.

  • MM is the product of all the moduli M=m₁∗m₂∗...∗mkM = m₁ * m₂ * ... * mk.

  • y₁,y₂,...,yky₁, y₂, ..., yk are the multiplicative inverses of $m1, m₂, ..., mk$ modulo and their respective moduli.

Flowchart to find the solution
Flowchart to find the solution

Theorem example

Let’s illustrate the Chinese remainder theorem with an example:

Suppose you have the following system of congruences:

To find the unique solution, follow these steps:

  1. Calculate M=7∗5∗9=315M = 7* 5*9 = 315.

  2. Calculate:

    1. m₁=M/7=45m₁ = M / 7 = 45

    2. m₂=M/5=63m₂ = M / 5= 63

    3. m₃=M/9=35m₃ = M / 9 = 35

  3. Calculate the multiplicative inverses:

    1. y₁y₁ is the multiplicative inverse of m₁(mod 7)m₁(mod~7), which is 55 because 45∗5≡1(mod 7)45 * 5 ≡ 1(mod~7).

    2. y₂y₂ is the multiplicative inverse of m₂(mod 5)m₂(mod~5), which is 22 because 63∗2≡1(mod 5)63 * 2 ≡ 1 (mod~5).

    3. y₃y₃ is the multiplicative inverse of m₃(mod 9)m₃(mod~9), which is 88 because 35∗8≡1(mod 9)35 * 8 ≡ 1 (mod~9).

  4. Now, apply the CRT formula:

  1. Calculate the result:

  1. The solution to the system of congruences is x≡1877(mod 315)x ≡ 1877 (mod~315).

Knowledge test

Let's test your understanding of the theorem by the quiz given below:

Chinese remainder theorem

1

If x≡1(mod  3)x ≡ 1 (mod\;3), x≡3(mod  7)x ≡ 3(mod\;7) and x≡4(mod  11)x ≡ 4 (mod\;11) what would be the value of MM?

A)

231

B)

12

C)

167

Question 1 of 30 attempted

Applications

The Chinese remainder theorem has practical applications in various areas, including:

  1. Cryptography: It is used in RSA encryption and decryption algorithms to speed up calculations involving large integers.

  2. Computer Science: CRT is employed in computer algorithms for error detection and correction, particularly in data transmission and storage.

  3. Number Theory: It plays a vital role in solving problems related to Diophantine equations and modular arithmetic.

  4. Coding Theory: CRT is used to design error-correcting code, which are crucial for reliable data transmission and storage.

Conclusion

The Chinese remainder theorem is a powerful mathematical tool for solving sets of linear congruences, distinguished by moduli that are coprime with each other. Its broad applicability extends across various domains, positioning it as a fundamental principle in both theoretical mathematics and practical applications. Mastery of the CRT can enhance problem-solving skills and open doors to opportunities in cryptography, computer science, and number theory.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved