Chinese Remainder Theorem

Abstract Algebra · Axiom Academy

REAL WORLD Chinese Remainder Theorem Discover how ancient mathematics powers modern cryptography through secret sharing schemes and ring isomorphisms. Imagine you're a CEO with a critical password to your company's vault. You want to ensure: No single person can access it alone (security) Any 2 out of 3 executives together can recover it (redundancy) The secret remains hidden until reconstruction Solution: Use the Chinese Remainder Theorem to split the secret into shares! The Chinese Remainder Theorem lets us represent our secret x = 42 as a system of congruences using coprime moduli. Key Insight: We chose moduli 5, 7, and 11 because they're coprime ( ). Their product is , so any secret from 0 to 384 can be uniquely represented! The Chinese Remainder Theorem is really about a ring isomorphism . When gcd(m, n) = 1, we have: What this means: Every number in Z₃₈₅ corresponds to a unique triple in Z₅ × Z₇ × Z₁₁, and vice versa. This bijection preserves both addition and multiplication! Solving Simultaneous Congruences Now let's see how to recover the secret from any 2 shares. The CRT provides an explicit formula! Enter congruences (or use our example): Why do we need gcd(m₁, m₂) = 1? Now you can play the role of the executives! Enter any 2 shares to recover the secret. When , the map given by is a ring isomorphism. The solution to the system is unique modulo , where all moduli are pairwise coprime. The solution uses: , where M_i = M/m_i and y_i is the inverse of .

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