Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 18m 45s17 days 22 hours 18 minutes 45 seconds.

Advanced - Number Theory · 4:22

Chinese Remainder Theorem & Garner's Algorithm

For pairwise coprime moduli, the system x ≡ aᵢ (mod mᵢ) has exactly one solution modulo their product: x ≡ 2, 3, 2 (mod 3, 5, 7) gives 23 (mod 105). It is built from Bézout switches or, more safely, by merging one congruence at a time; with shared factors the remainders must agree modulo each gcd and the answer is unique modulo the lcm. Garner's algorithm rebuilds a number from its residues as mixed-radix digits, which lets big integers be carried as residues modulo many primes.

You will learn

State the Chinese Remainder Theorem and solve a small system with Bézout switches
Merge congruences one at a time with extended Euclid, avoiding 64-bit overflow
Handle moduli that are not coprime: check aᵢ ≡ aⱼ (mod gcd), answer modulo the lcm, or split into prime powers
Use Garner's algorithm to rebuild a number from residues modulo several primes, including the normalisation and sign rules

Chapters

PreviousLinear Congruence Equations NextEuler's Totient Function and Euler's Theorem