A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
If n₁, n₂, …, nₖ are pairwise coprime, the system x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), … has a unique solution modulo n₁n₂⋯nₖ. The CRT enables efficient computation by reducing large moduli to smaller ones and has applications in cryptography and parallel computation.
The Chinese Remainder Theorem is, at its heart, a statement about independence. From your work with the Euclidean algorithm, you know what it means for two numbers to be coprime — their greatest common divisor is 1, meaning they share no prime factors. When two moduli are coprime, knowing a number's remainder mod one gives you absolutely no information about its remainder mod the other. This independence is the key insight: if you can freely specify remainders for each modulus separately, then every combination of remainders can be achieved by some number.
The concrete statement is this: if n₁, n₂, …, nₖ are pairwise coprime (every pair has gcd 1), then the system x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), … always has a solution, and that solution is unique modulo N = n₁n₂⋯nₖ. Think of it as a coordinate system: the remainders (a₁, a₂, …, aₖ) uniquely identify x among all integers from 0 to N−1, just as (x, y) coordinates uniquely identify a point in the plane.
The constructive proof gives you an algorithm. For each modulus nᵢ, define Mᵢ = N/nᵢ — the product of all the other moduli. Since nᵢ and Mᵢ are coprime (nᵢ shares no factors with any other modulus), the Euclidean algorithm finds an inverse yᵢ such that Mᵢyᵢ ≡ 1 (mod nᵢ). Then the solution is x = a₁M₁y₁ + a₂M₂y₂ + ⋯ + aₖMₖyₖ (mod N). Each term aᵢMᵢyᵢ contributes exactly aᵢ in the i-th congruence and zero in all others, because Mᵢ is divisible by every nⱼ with j ≠ i.
Applications of CRT appear wherever you want to reduce a hard computation modulo a large number to easier computations modulo smaller numbers. In cryptography, RSA implementations use CRT to speed up modular exponentiation by working modulo p and q separately and combining results. In computer arithmetic, CRT underpins residue number systems, where integers are represented as tuples of small remainders and arithmetic is done component-wise in parallel. Whenever you see a system of simultaneous modular constraints, CRT tells you whether a solution exists and how to find it — turning what looks like a global constraint satisfaction problem into independent local problems.