Engineering / Mathematics — Integer Foundations
The Chinese Remainder Theorem
The Chinese remainder theorem as a ring isomorphism, its constructive proof, and its role in decomposing modular computation.
Executive summary
The Chinese remainder theorem states that a system of congruences with pairwise coprime moduli has a unique simultaneous solution modulo the product. Stated that way it sounds like a technique for puzzles.
Stated as a ring isomorphism it is a structural decomposition: arithmetic modulo a composite splits into independent arithmetic modulo each prime power. That version is what drives the algorithms.
Learning objectives
- State the theorem in both congruence and isomorphism form.
- Construct the solution explicitly.
- Explain how the decomposition is exploited computationally.
01The theorem
Chinese remainder theorem
Let n₁, ..., nₖ be pairwise coprime positive integers with product N. Then for any residues a₁, ..., aₖ the system
x ≡ aᵢ (mod nᵢ) for each i
has a solution, unique modulo N.
The isomorphism form says the same thing more usefully.
Z_N ≅ Z_{n₁} × Z_{n₂} × ··· × Z_{nₖ}This is an isomorphism of rings, so it respects both addition and multiplication. Restricting to units gives Z_N* ≅ Z_{n₁}* × ··· × Z_{nₖ}*, from which the multiplicativity of Euler's phi function follows immediately.
02Constructing the solution
Chinese remaindering
pairwise coprime moduli nᵢ and residues aᵢthe unique x mod N satisfying all congruences- Compute N = n₁ ··· nₖ.
- For each i, set Nᵢ = N / nᵢ. Note gcd(Nᵢ, nᵢ) = 1 by pairwise coprimality.
- For each i, compute Mᵢ = Nᵢ⁻¹ mod nᵢ using extended Euclid.
- Return x = Σ aᵢ · Nᵢ · Mᵢ mod N.
O(len(N)²) bit operationsThe construction works because NᵢMᵢ is congruent to 1 modulo nᵢ and to 0 modulo every other modulus. Each term therefore contributes aᵢ to its own congruence and nothing to the others — the modular analogue of a basis of indicator functions.
An incremental variant, sometimes preferable, solves the congruences two at a time using Bezout coefficients directly, avoiding the computation of the full product until the end.
03Why the decomposition matters computationally
Parallel arithmetic
Computations modulo a large N split into independent computations modulo each nᵢ, all of which fit in smaller words and can proceed simultaneously.
Controlled coefficient growth
Exact integer computations that would produce enormous intermediate values can be run modulo several primes and reconstructed, bounding the size of every intermediate.
Structural analysis
Questions about Z_N* reduce to the same questions about each Z_{p^k}*, which is how the structure of the group of units is determined.
Cryptographic speedup
RSA private-key operations are performed modulo p and q separately and recombined, giving roughly a fourfold speedup over working modulo the product.
04Frequently asked questions
Why is the theorem named after China?
The earliest known statement of a problem of this type appears in a fourth-century Chinese text by Sun Zi, concerning counting an unknown quantity of objects by remainders. The general theorem was formalised much later.
What happens when the moduli are not coprime?
The system is solvable exactly when each pair of congruences agrees modulo the gcd of its two moduli, and the solution is then unique modulo the lcm rather than the product. The ring map still exists but is no longer an isomorphism.
Does the theorem help with factoring?
Not directly — applying it requires already knowing the factorisation. It is a tool for those who hold the factorisation, which is why it accelerates RSA decryption for the key holder but offers nothing to an attacker.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 20-24.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.