The Chinese remainder theorem is a theorem in number theory stating that congruences with pairwise coprime positive integer moduli can be solved simultaneously, with a unique solution modulo the product of those moduli. It provides both a way to reconstruct an integer from its remainders and a structural description of modular arithmetic: computation modulo a product of coprime numbers is equivalent to independent computation modulo each factor. Generalized forms cover noncoprime moduli, polynomials, and ideals in commutative rings.
Statement
Let be integers greater than , and suppose they are pairwise coprime:
where denotes the greatest common divisor. For any integers , the simultaneous congruences
have a solution. If
then any two solutions differ by a multiple of . Equivalently, there is exactly one solution in the range , and all integer solutions have the form
The condition is pairwise coprimality, not merely that the greatest common divisor of all the moduli is . For example, have collective greatest common divisor , but no two are coprime.
Uniqueness is therefore uniqueness modulo , not uniqueness as an unrestricted integer.
Constructive formula and proof
Set
Since the moduli are pairwise coprime, . Consequently, has a multiplicative inverse modulo : there is an integer such that
These inverses can be computed using the extended Euclidean algorithm. Their existence also follows from Bézout's identity, which expresses the greatest common divisor of two integers as an integer linear combination of them.
A solution is
To verify existence, consider the sum modulo a particular . Every term with vanishes because divides . The remaining term satisfies
Thus the sum satisfies every congruence.
For uniqueness, let and be solutions. Each divides . Because the moduli are pairwise coprime, their product also divides , so
This gives a constructive proof: it both establishes the theorem and supplies an algorithm for finding the solution.
Classical example
Consider
Here , and
Suitable inverses are , , and , since
The reconstruction formula gives
Hence the least nonnegative solution is , and the complete set of solutions is
The residues do not distinguish from , , or any other integer in this residue class. A bound or a prescribed interval is needed to identify one particular integer.
Noncoprime moduli
Pairwise coprimality guarantees a solution for every choice of remainders. Without it, existence depends on compatibility.
For arbitrary positive integer moduli , the system
has a solution if and only if
for every pair . Whenever a solution exists, it is unique modulo
where is the least common multiple.
The necessity follows because a common divisor of and must divide . Sufficiency can be proved by merging congruences successively.
For two congruences,
write . The second congruence becomes
With , this is solvable exactly when . Dividing by then gives
whose coefficient is invertible modulo . The merged solution is determined modulo .
For example,
is compatible because both remainders are odd. Its solution is
By contrast, replacing the second remainder with makes the system inconsistent: it would require to be both odd and even.
Algebraic interpretation
The theorem can be expressed as an isomorphism of rings:
Here is the ring of integer residue classes modulo , and the product on the right uses coordinatewise addition and multiplication.
The map
is a ring homomorphism. The theorem establishes that it is bijective: every tuple of residues is represented, and each has exactly one preimage modulo .
This formulation explains why reconstruction is compatible with arithmetic. Integers can be added or multiplied separately in the smaller modular rings, and the reconstructed result agrees with addition or multiplication modulo .
The elements
used in the constructive proof satisfy
They are mutually orthogonal instances of idempotence and serve as selectors for the product's coordinates.
Generalization to ideals
Let be a commutative ring with identity, and let be ideals that are pairwise comaximal, meaning
Then
For finitely many pairwise comaximal ideals,
The integer theorem is the case and . Unlike integers, ideals in an arbitrary commutative ring need not satisfy a sufficient compatibility criterion based solely on pairwise agreement; the comaximal hypothesis is central to this product decomposition.
Polynomial version
Let be a field, and let be pairwise coprime nonconstant polynomials in . Given arbitrary polynomials , there is a polynomial satisfying
for every , uniquely modulo . It therefore has a unique representative of degree less than
Taking for distinct elements turns the congruences into prescribed values,
The polynomial remainder theorem thus connects the Chinese remainder theorem with polynomial interpolation, including the Lagrange interpolation formula. Powers similarly encode higher-order local polynomial data.
Historical development
The theorem takes its name from an early Chinese remainder problem recorded in the Sunzi Suanjing (Mathematical Classic of Master Sun), whose precise date of composition is uncertain. The problem asks for a number that leaves remainders , , and when divided by , , and , respectively. Its least positive solution is .
In 1247, Qin Jiushao's Shushu Jiuzhang (Mathematical Treatise in Nine Sections) presented more general methods for remainder problems, including procedures for finding the modular inverses needed in reconstruction. The familiar modern theorem abstracts these computational methods into a statement about arbitrary finite systems of congruences. Its formulation through ideals and quotient rings belongs to the later development of abstract algebra.
Algorithms and applications
Exact computation
The theorem supports computations with large integers by replacing one large calculation with several calculations modulo smaller, pairwise coprime numbers. The modular computations can often be performed independently, making the method suitable for parallel computing.
If an integer result is known to lie in an interval containing fewer than consecutive integers, its residues modulo factors with product determine it uniquely within that interval. For example, a bound permits unique signed reconstruction when .
This principle is used in exact polynomial arithmetic, determinant computation, and other symbolic algorithms. Modular reconstruction gives a residue class; a proven size bound or another verification step is needed to identify the intended unrestricted integer.
Cryptography
In the RSA cryptosystem, a private-key operation modulo , with distinct primes and , can be performed separately modulo and modulo , followed by Chinese remainder reconstruction. The smaller modular exponentiations usually make this faster than a direct computation modulo .
This acceleration requires implementation safeguards. A faulty result that is correct modulo one prime but not the other can, under suitable conditions, reveal a factor of . The theorem supplies the arithmetic decomposition, not protection against implementation faults.
Solving modular equations
When a modulus has a factorization into coprime prime powers,
a polynomial congruence modulo can be solved separately modulo each prime power. Every compatible choice of local roots then reconstructs to exactly one root modulo . Consequently, the number of roots modulo is the product of the numbers of roots modulo the prime-power factors.
Computational limitations
The theorem does not itself find a useful factorization of a large modulus. Efficient arithmetic modulo its factors presupposes that those factors are already available.
Nor does it make exact reconstruction insensitive to error: changing even one remainder can produce a very different reconstructed integer. Error-tolerant reconstruction requires additional assumptions, redundancy, or specialized methods beyond the basic theorem.