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:
- Find the global modulus (N): Multiply all the individual moduli together. N = n₁ × n₂ × ... × nₖ
- Calculate the partial products (Nᵢ): For each
congruence, divide the global modulus
Nby that specific congruence's modulusnᵢ. Nᵢ = N / nᵢ - Find the modular inverses (yᵢ): For each
congruence, find a number
yᵢthat, when multiplied byNᵢ, leaves a remainder of 1 when divided bynᵢ. Nᵢ × yᵢ ≡ 1 (mod nᵢ) - 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ₖ) - Find the smallest positive solution: Divide the sum
by the global modulus
Nand 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.