Interactive CRT Solver
The Legend
General Han Xin (circa 200 BCE) needed to count his troops after a battle but didn't want enemies to know his strength. Instead of a direct count, he ordered soldiers to line up in rows of 3, then 5, then 7, noting only the remainders. From just three remainders, he could deduce the total number—a technique now formalized as the Chinese Remainder Theorem (CRT).
The Mathematics
Chinese Remainder Theorem: Given pairwise coprime moduli m₁, m₂, ..., mₙ and remainders r₁, r₂, ..., rₙ, there exists a unique solution x modulo M = m₁·m₂·...·mₙ such that:
x ≡ r₁ (mod m₁)
x ≡ r₂ (mod m₂)
x ≡ r₃ (mod m₃)
Construction: For each i, compute Mᵢ = M/mᵢ, then find yᵢ such that Mᵢ·yᵢ ≡ 1 (mod mᵢ). The solution is: x = Σ(rᵢ·Mᵢ·yᵢ) mod M
Example
If soldiers leave remainders 2, 3, 2 when arranged in rows of 3, 5, 7:
• M = 3×5×7 = 105
• Solution: x ≡ 23 (mod 105)
• Possible troop counts: 23, 128, 233, 338, ...