Chinese remainder theorem

For pairwise coprime positive integers m₁, m₂, …, mₖ, and any integers a₁, a₂, …, aₖ, the system x ≡ aᵢ (mod mᵢ) for i = 1, …, k has a solution. Any two solutions differ by a multiple of M = m₁m₂⋯mₖ, so the solution is unique modulo M. Equivalently, there is exactly one representative x in the range 0 ≤ x < M. Pairwise coprime means that every two different moduli have greatest common divisor 1.

Consider x ≡ 2 (mod 3), x ≡ 3 (mod 5), and x ≡ 2 (mod 7). The moduli are pairwise coprime and their product is 105. The number 23 satisfies all three conditions: dividing it by 3 leaves remainder 2, by 5 leaves remainder 3, and by 7 leaves remainder 2. The theorem guarantees that every integer satisfying the system is congruent to 23 modulo 105; thus 23 is the unique solution in the range from 0 to 104.

One construction sets M = m₁m₂⋯mₖ and Mᵢ = M/mᵢ. Because mᵢ is coprime to Mᵢ, the extended Euclidean algorithm finds an integer uᵢ with uᵢMᵢ ≡ 1 (mod mᵢ). Then x = Σᵢ aᵢuᵢMᵢ satisfies every congruence: modulo mᵢ, its own term reduces to aᵢ and the other terms reduce to zero. Reducing this x modulo M gives the unique representative between 0 and M−1.

Pairwise coprimality is a sufficient condition that ensures a solution for every choice of remainders; it is not necessary for every particular system to have a solution. For two congruences x ≡ a (mod m) and x ≡ b (mod n), a solution exists exactly when a and b agree modulo gcd(m,n), and any solutions are then unique modulo lcm(m,n). For example, x ≡ 1 (mod 4) and x ≡ 3 (mod 6) are compatible because both residues are 1 modulo 2; x = 9 is a solution, and solutions repeat modulo 12.

A remainder problem that became associated with the theorem appears in the ancient Chinese mathematical text Sunzi Suanjing: find a number that leaves remainders 2, 3, and 2 upon division by 3, 5, and 7. This example has the solution 23 modulo 105. The general theorem is a broader mathematical result than that early problem. Today, the theorem is useful when a calculation involving a large integer can be split into smaller calculations modulo coprime numbers and then recombined. Applications include algorithms for large-integer arithmetic and methods in cryptography, including CRT-based techniques for RSA.