Chinese Remainder Theorem

Cryptography · Axiom Academy

LESSON Chinese Remainder Theorem Solving systems of modular congruences and applications in cryptography 1. Historical Origins: Sun Tzu's Problem The Chinese Remainder Theorem first appeared in the 3rd century AD in Sun Tzu's Suan Ching (Mathematical Classic): "There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?" In modern notation, this asks us to find x such that: The animation below shows how different remainders constrain the possible values of x until a unique solution emerges within a certain range. 2. The Chinese Remainder Theorem The theorem provides both existence and uniqueness guarantees for solutions to systems of modular congruences. Theorem: Let n₁, n₂, ..., nₖ be pairwise coprime positive integers (i.e., gcd(nᵢ, nⱼ) = 1 for i ≠ j), and let a₁, a₂, ..., aₖ be any integers. Then the system: has a unique solution modulo N = n₁ · n₂ · ... · nₖ. Existence: A solution always exists Uniqueness: The solution is unique modulo N Requirement: The moduli must be pairwise coprime The CRT provides an explicit construction for finding the solution using modular inverses. Compute N = n₁ · n₂ · ... · nₖ (the product of all moduli) For each i, compute Nᵢ = N / nᵢ For each i, find Mᵢ such that Nᵢ · Mᵢ ≡ 1 (mod nᵢ) using the Extended Euclidean Algorithm The solution is: x ≡ Σ(aᵢ · Nᵢ · Mᵢ) (mod N) Let's solve Sun Tzu's original problem:

This is the written version of the interactive lesson above. See the full Cryptography course.