✦ScienexySCIENCE KNOWLEDGE LIBRARY
theorem · SCI-MAT-002-077

Chinese Remainder Theorem

The Chinese Remainder Theorem states that a system of congruences with pairwise relatively prime moduli has a unique solution modulo the product of those moduli.

x ≡ Σ(aᵢNᵢMᵢ) (mod N), where N = ∏nᵢ, Nᵢ = N/nᵢ, and NᵢMᵢ ≡ 1 (mod nᵢ)

Explanation

The Chinese Remainder Theorem is a fundamental result in number theory that provides a method for solving systems of simultaneous congruences. Suppose a system is given by x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), and so on. If the moduli n₁, n₂, ..., nₖ are pairwise relatively prime, then the system has a solution that is unique modulo N = n₁n₂...nₖ. The theorem can be applied using a constructive method: calculate N, set Nᵢ = N/nᵢ, find the modular inverse of Nᵢ modulo nᵢ, and combine the resulting terms. The theorem also has a more general form for moduli that are not pairwise relatively prime, where compatibility conditions between the congruences must be satisfied. It is widely used in computational number theory, cryptography, and efficient arithmetic.

Variables

X

An integer satisfying all congruences.

Aᵢ

The required remainder in the i-th congruence.

Nᵢ

The modulus of the i-th congruence.

N

The product of all moduli.

Nᵢ

The quotient N/nᵢ.

Mᵢ

The modular inverse of Nᵢ modulo nᵢ.

Example or application

Problem

Solve x ≡ 2 (mod 3) and x ≡ 3 (mod 5).

Solution

The moduli 3 and 5 are relatively prime. Numbers congruent to 2 modulo 3 are 2, 5, 8, 11, 14, and so on. Among these, 8 is congruent to 3 modulo 5. Therefore, the solution is x ≡ 8 modulo 15, since the product of the moduli is 3 × 5 = 15.

Answer

x ≡ 8 (mod 15)

Text

The Chinese Remainder Theorem transforms a system of congruences with pairwise coprime moduli into one congruence modulo their product. The resulting residue class contains every integer satisfying the entire system.

Key Points

  • The theorem solves systems of simultaneous congruences.

  • Pairwise relatively prime moduli guarantee a solution.

  • The solution is unique modulo the product of the moduli.

  • The constructive method uses modular inverses.

  • The general theorem also handles compatible systems with non-coprime moduli.

  • The theorem can combine several smaller modular calculations into one larger congruence.

Applications

  • Public-key cryptography and RSA optimization.

  • Computer arithmetic with large integers.

  • Efficient modular computations.

  • Reconstructing integers from their remainders.

  • Solving scheduling and periodicity problems.

Learning Outcomes

  • State the Chinese Remainder Theorem.

  • Determine whether moduli are pairwise relatively prime.

  • Solve simple systems of simultaneous congruences.

  • Explain why the solution is unique modulo the product of the moduli.

Practice Questions

  • Solve x ≡ 1 (mod 3) and x ≡ 2 (mod 5).

  • Solve x ≡ 2 (mod 5) and x ≡ 4 (mod 7).

  • Explain why pairwise relative primality is important in the theorem.

  • Find the smallest positive integer satisfying x ≡ 1 (mod 4), x ≡ 2 (mod 5), and x ≡ 3 (mod 7).

  • What changes when the moduli are not relatively prime?

Related Concepts

  • Congruence Relations

  • Modular Inverses

  • Linear Congruences

  • Greatest Common Divisor

  • Modular Arithmetic

Common Mistakes

  • Assuming the moduli are pairwise relatively prime without checking.

  • Confusing uniqueness modulo N with a single integer solution.

  • Calculating modular inverses with the wrong modulus.

  • Combining congruences with incompatible non-coprime moduli.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Kenneth H. Rosen, Elementary Number Theory and Its Applications
  • David M. Burton, Elementary Number Theory

Suggest a correction or source · More in Arithmetic & Number Theory