Chinese Remainder Theorem Calculator
Solve systems of congruences using the Chinese Remainder Theorem
System of Congruences
Enter your congruences:
Solution
Verification:
Step-by-Step Solution:
Example: Candy Distribution Problem
Problem: Find a number x such that:
• When divided by 3, remainder is 1
• When divided by 4, remainder is 2
• When divided by 5, remainder is 3
x ≡ 1 (mod 3)
x ≡ 2 (mod 4)
x ≡ 3 (mod 5)
Solution: x ≡ 58 (mod 60)
Algorithm Steps
Calculate N
N = n₁ × n₂ × ... × nₖ
Find Mᵢ values
Mᵢ = N / nᵢ for each i
Solve for yᵢ
Mᵢ × yᵢ ≡ 1 (mod nᵢ)
Combine
x = Σ(aᵢ × Mᵢ × yᵢ) mod N
Requirements
All moduli must be greater than 1
Moduli must be pairwise coprime
Solution is unique modulo N
Works for any number of congruences
Understanding the Chinese Remainder Theorem
What is the Chinese Remainder Theorem?
The Chinese Remainder Theorem (CRT) provides a way to solve systems of simultaneous congruences with pairwise coprime moduli. It guarantees a unique solution modulo the product of all moduli.
Key Requirements
- •Moduli must be pairwise coprime (gcd of any pair = 1)
- •All moduli must be positive integers greater than 1
- •Solution exists and is unique modulo N = n₁ × n₂ × ... × nₖ
Mathematical Foundation
System of Congruences:
x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
⋮
x ≡ aₖ (mod nₖ)
Applications
- •Cryptography (RSA algorithm)
- •Computer science algorithms
- •Calendar calculations
- •Number theory problems
Historical Context
Despite its name, the Chinese Remainder Theorem was not originally from China. The earliest known statement appears in the work of the Chinese mathematician Sun Tzu (not the military strategist) around 3rd-5th century CE. The theorem was later rediscovered and formalized by European mathematicians in the 18th century.