Solving Congruences with the Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a fundamental principle in number theory used to solve systems of simultaneous linear congruences. It guarantees a unique solution when looking for a single number that leaves specific remainders when divided by several different divisors. This article explains the core conditions required for the theorem to work, the step-by-step mathematical algorithm used to construct the unique solution, and a practical example demonstrating the exact resolution of a multi-congruence system.

Understanding the Problem

In modular arithmetic, a congruence states that two numbers have the same remainder when divided by a specific integer, called the modulus. A system of simultaneous congruences asks you to find a single unknown integer, x, that satisfies multiple modular equations at the same time:

  • x ≡ a₁ (mod n₁)
  • x ≡ a₂ (mod n₂)
  • ...
  • x ≡ aₖ (mod nₖ)

Here, a₁, a₂, ..., aₖ are the given remainders, and n₁, n₂, ..., nₖ are the given moduli (divisors).

The Core Requirement: Coprime Moduli

The Chinese Remainder Theorem only guarantees a unique solution if the moduli are pairwise coprime. This means that no two moduli in the system share any common factors other than 1. Mathematically, the greatest common divisor (GCD) of any pair of moduli must be 1:

GCD(nᵢ, nⱼ) = 1 for all i ≠ j.

If this condition is met, the theorem states that there is exactly one unique solution for x between 0 and the product of all the moduli.

The Step-by-Step Solution Algorithm

To solve a system of congruences using the Chinese Remainder Theorem, you construct the solution by isolating each congruence, solving a localized version of it, and adding the results together.

Follow these five steps to find x:

  1. Find the global modulus (N): Multiply all the individual moduli together. N = n₁ × n₂ × ... × nₖ
  2. Calculate the partial products (Nᵢ): For each congruence, divide the global modulus N by that specific congruence's modulus nᵢ. Nᵢ = N / nᵢ
  3. Find the modular inverses (yᵢ): For each congruence, find a number yᵢ that, when multiplied by Nᵢ, leaves a remainder of 1 when divided by nᵢ. Nᵢ × yᵢ ≡ 1 (mod nᵢ)
  4. Sum the components: Multiply the remainder (aᵢ), the partial product (Nᵢ), and the modular inverse (yᵢ) for each congruence, and add them all together. Sum = (a₁ × N₁ × y₁) + (a₂ × N₂ × y₂) + ... + (aₖ × Nₖ × yₖ)
  5. Find the smallest positive solution: Divide the sum by the global modulus N and take the remainder. x ≡ Sum (mod N)

Why This Construction Works

The brilliance of the theorem lies in Step 2 and Step 3. Because Nᵢ is the product of all moduli except nᵢ, Nᵢ is automatically a multiple of every other modulus in the system. Therefore, when you check the final sum against a specific modulus (for example, n₁), all the other terms in the sum become zero because they are multiples of n₁.

You are left with only the first term: a₁ × N₁ × y₁ (mod n₁). Because you specifically chose y₁ so that N₁ × y₁ ≡ 1 (mod n₁), this term simplifies to a₁ × 1, leaving the exact remainder a₁ required by the first equation. This applies simultaneously to every equation in the system.

A Practical Example

Consider the classic system of three congruences:

  • x ≡ 2 (mod 3)
  • x ≡ 3 (mod 5)
  • x ≡ 2 (mod 7)

First, verify the moduli (3, 5, and 7) are pairwise coprime. Since they are all prime numbers, they share no factors other than 1. The theorem applies.

Step 1: Find the global modulus (N) N = 3 × 5 × 7 = 105

Step 2: Calculate the partial products (Nᵢ)

  • N₁ = 105 / 3 = 35
  • N₂ = 105 / 5 = 21
  • N₃ = 105 / 7 = 15

Step 3: Find the modular inverses (yᵢ)

  • For y₁: 35 × y₁ ≡ 1 (mod 3). Since 35 divided by 3 leaves a remainder of 2, this simplifies to 2 × y₁ ≡ 1 (mod 3). By testing values, y₁ = 2 works because 2 × 2 = 4, and 4 leaves a remainder of 1 when divided by 3. So, y₁ = 2.
  • For y₂: 21 × y₂ ≡ 1 (mod 5). Since 21 leaves a remainder of 1 when divided by 5, this simplifies to 1 × y₂ ≡ 1 (mod 5). Therefore, y₂ = 1.
  • For y₃: 15 × y₃ ≡ 1 (mod 7). Since 15 leaves a remainder of 1 when divided by 7, this simplifies to 1 × y₃ ≡ 1 (mod 7). Therefore, y₃ = 1.

Step 4: Sum the components Multiply aᵢ × Nᵢ × yᵢ for each row and add them:

  • Row 1: 2 × 35 × 2 = 140
  • Row 2: 3 × 21 × 1 = 63
  • Row 3: 2 × 15 × 1 = 30

Sum = 140 + 63 + 30 = 233

Step 5: Find the smallest positive solution Take the sum modulo N (105): x = 233 (mod 105)

233 divided by 105 is 2, with a remainder of 23. x = 23

To verify: 23 divided by 3 leaves a remainder of 2; 23 divided by 5 leaves a remainder of 3; and 23 divided by 7 leaves a remainder of 2. The system is solved.