Chinese Remainder Theorem

Number Theory · Axiom Academy

LESSON Chinese Remainder Theorem Solving systems of simultaneous congruences through ancient mathematical wisdom The Chinese Remainder Theorem addresses the question: given multiple modular constraints, when does a solution exist, and how do we find it? Let n 1 , n 2 , ..., n k be pairwise coprime positive integers (i.e., gcd( n i , n j ) = 1 for i ≠ j ). Then the system of congruences: has a unique solution modulo N = n 1 × n 2 × ... × n k . The CRT provides an explicit construction for finding the solution. Here's the systematic approach: Step 1: Compute N = n 1 × n 2 × ... × n k Step 2: For each i , let N i = N / n i Step 3: Find M i such that N i × M i ≡ 1 (mod n i ) Here, M i is the modular inverse of N i modulo n i , which exists because gcd( N i , n i ) = 1. Let's solve a concrete system to see the CRT in action: Step 2: N 1 = 105/3 = 35, N 2 = 105/5 = 21, N 3 = 105/7 = 15 35 M 1 ≡ 1 (mod 3) → M 1 = 2 (since 35 × 2 = 70 ≡ 1 mod 3) 21 M 2 ≡ 1 (mod 5) → M 2 = 1 (since 21 × 1 = 21 ≡ 1 mod 5) 15 M 3 ≡ 1 (mod 7) → M 3 = 1 (since 15 × 1 = 15 ≡ 1 mod 7) 4. Historical Context and Applications The Chinese Remainder Theorem has a rich history spanning over 1800 years and continues to play a vital role in modern mathematics and computer science. The theorem first appeared in the 3rd century CE in the Chinese mathematical text Sunzi Suanjing (Master Sun's Mathematical Manual). The classic problem asked:

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