A reconstruction technique that combines residues of an integer (or polynomial) modulo several pairwise coprime moduli to recover the original integer (or polynomial) modulo the product of the moduli, with uniqueness guaranteed modulo that product.

Principle

By the Chinese Remainder Theorem, a consistent system of congruences x ≡ r_i (mod m_i) with gcd(m_i,m_j)=1 has a unique solution modulo M = ∏ m_i; constructive algorithms assemble the residues using modular inverses or mixed-radix expansions to recover x mod M.

Demonstration

Given residues x ≡ 2 (mod 3), x ≡ 3 (mod 5), and x ≡ 2 (mod 7), compute the unique solution modulo 105 by combining residues (here x ≡ 23 (mod 105)), thereby reconstructing the integer class from its modular pieces.

Misapplication

Applying CRT when moduli are not pairwise coprime without checking consistency, or believing that CRT reconstructs the absolute integer rather than only the class modulo the product, can lead to incorrect global reconstruction or ambiguity.

Consequence

Proper CRT reconstruction enables modular algorithms: perform heavy computations modulo small primes and combine results to obtain values modulo large composite moduli, provides efficient parallelization and underlies rational/integer reconstruction methods.

Reversal

Reduction modulo each modulus is the reverse operation: given an integer, compute its residues. In some algorithms, CRT is reversed by splitting a modular computation into independent small-modulus computations for efficiency.

Boundary

Requires pairwise coprime moduli for the standard uniqueness result; generalizations exist for noncoprime moduli but require compatibility checks and may yield multiple or no solutions; also integer bounds are needed to lift a residue class to a canonical integer.

Semantic Tension

Tension with Hensel lifting and rational reconstruction: CRT combines independent modular data globally, while Hensel lifting improves local p-adic precision; rational reconstruction may require both CRT and bounds to recover small rational numbers.

Synthesis

Chinese Remainder Reconstruction is the constructive assembly of modular residues into a unique residue class modulo the product of pairwise coprime moduli, enabling global recovery from local modular computations and serving as a backbone of many modular algorithms.