Mathematics
The Chinese Remainder Theorem and Modular Arithmetic
Quick fact
The Chinese Remainder Theorem guarantees that, given several remainders modulo pairwise coprime moduli, there is exactly one integer modulo the product of those moduli that satisfies all conditions at once—this is what allows RSA decryption to be performed several times faster than naive exponentiation.
Why this is interesting
Imagine you have a puzzle: a number leaves a remainder of 2 when divided by 3 and a remainder of 3 when divided by 5—but can you find it? The answer might surprise you: there isn’t just one, but an infinite family of solutions, and they all share a simple pattern.
Read the full explanation
Understanding The Chinese Remainder Theorem and Modular Arithmetic
Start with the idea of modular arithmetic: when you divide a number by a modulus, you care only about the remainder. Now, suppose you have multiple such remainders for different moduli. The Chinese Remainder Theorem says that if the moduli are pairwise coprime (meaning they have no common factors other than 1), then there is exactly one number modulo the product of all the moduli that satisfies all the remainder conditions simultaneously. For example, take the moduli 3 and 5, which are coprime. Any number that leaves remainder 2 modulo 3 and remainder 3 modulo 5 can be found by checking numbers modulo 15. The unique solution is 8, because 8 ≡ 2 (mod 3) and 8 ≡ 3 (mod 5). Adding 15 repeatedly gives other solutions like 23, 38, etc., but all are equivalent modulo 15. The key idea is that the moduli are independent—since they share no factors, the information from each one doesn't conflict, and they can always be combined uniquely up to the product.
A deeper explanation
The CRT works because of the fundamental structure of integers modulo a product. If N = n1 × n2 × ... × nk with all ni pairwise coprime, then there is a one-to-one correspondence between integers modulo N and tuples of remainders modulo each ni. Formally, the map that sends a residue modulo N to its vector of residues modulo each ni is a bijection, and it preserves addition and multiplication—it is a ring isomorphism. The mechanism behind this is that you can reconstruct the unique solution using a linear combination: for each i, find an integer Mi = N/ni. Since ni and Mi are coprime, Mi has a multiplicative inverse modulo ni. Then the solution is x ≡ Σ (ai × Mi × inv(Mi mod ni)) mod N, where ai is the desired remainder modulo ni. This construction works because each term is divisible by all other moduli, so it doesn't affect their remainders, while it contributes exactly ai modulo ni. This decomposition is not just a theoretical curiosity: it allows solving large modular problems piece by piece, making computations faster and easier to reason about, which is why it is essential in cryptography and computer arithmetic.