gen-define-the-chinese-remainder-theorem-and-give-one-short-work-e83d

Define the Chinese remainder theorem and give one short worked example.

# Chinese Remainder Theorem ## Definition The **Chinese Remainder Theorem** states that if you have a system of congruences: - x ≡ a₁ (mod n₁) - x ≡ a₂ (mod n₂) - ⋮ - x ≡ aₖ (mod nₖ) where n₁, n₂, ..., nₖ are **pairwise coprime** (gcd(nᵢ, nⱼ) = 1 for i ≠ j), then there exists a unique solution modulo N = n₁ · n₂ · ... · nₖ. ## Worked Example Find x such that: - x ≡ 2 (mod 3) - x ≡ 3 (mod 5) **Solution:** Since gcd(3,5) = 1, the moduli are coprime. N = 3 · 5 = 15. 1. Let N₁ = N/3 = 5 and N₂ = N/5 = 3 2. Find M₁ such that 5M₁ ≡ 1 (mod 3): - 5 ≡ 2 (mod 3), so 2M₁ ≡ 1 (mod 3) - M₁ = 2 works: 2 · 2 = 4 ≡ 1 (mod 3) ✓ 3. Find M₂ such that 3M₂ ≡ 1 (mod 5): - 3M₂ ≡ 1 (mod 5) - M₂ = 2 works: 3 · 2 = 6 ≡ 1 (mod 5) ✓ 4. Calculate: x = a₁N₁M₁ + a₂N₂M₂ = 2(5)(2) + 3(3)(2) = 20 + 18 = 38 5. Reduce: x ≡ 38 ≡ **8 (mod 15)** **Answer:** x = 8 (and all numbers of the form 8 + 15k)