From a remainder to a system
The congruence x ≡ a (mod n) means that n divides x−a. It describes an infinite class: a, a+n, a−n and every integer shift by n. A system asks for one integer belonging to all these classes at once. That intersection is the solution set, and it repeats with a common period.
The classical theorem
If the moduli are pairwise coprime, every choice of residues has a solution, unique modulo their product N. Having a GCD of 1 across all moduli together is not enough: every pair must have GCD 1. The difference of two solutions is divisible by each modulus and hence, by coprimality, by N. Uniqueness refers to a class, not a single integer. NIST DLMF, §27.15.
N=i∏ni,x=x0+kN,k∈Z Direct construction with inverses
For each row, Nᵢ=N/nᵢ contains every other modulus. Its inverse uᵢ modulo nᵢ exists by coprimality. The factor Nᵢuᵢ therefore leaves remainder 1 in its own row and 0 in all other rows. Multiplying by aᵢ and adding builds all the requested remainders at once.
ui=Ni−1(modni),x0=(i∑aiNiui)modN Every term can be checked separately before the sum is reduced. This constructive argument is developed in MIT lecture 5 notes.
When moduli share factors
A solution exists if and only if every pair of residues agrees modulo the GCD of its moduli. When it exists, its period is the least common multiple L. Using the product could leave out solutions when describing the family. For example, 32 modulo 60, 2 modulo 90 and 2 modulo 150 combine into 452 modulo 900, one of the official SageMath examples.
ai≡aj(modgcd(ni,nj))∀i<j,L=lcm(n1,…,ns) Merging two congruences
Given the accumulated class x≡r (mod M), write x=r+Mk and impose the next row x≡a (mod n). This gives Mk≡a−r (mod n). With g=GCD(M,n), the difference must be divisible by g. Dividing by g leaves coprime moduli M′=M/g and n′=n/g, and the inverse of M′ modulo n′ comes from the extended Euclidean algorithm.
k0=(ga−r(M′)−1)modn′,r′=(r+Mk0)mod(Mn′) The new class has period Mn′. If n′=1, the row was already implied by the accumulated class: take k₀=0 without inverting modulo 1. Repeating the procedure incorporates the whole system.
Sun Zi, step by step
The historical problem asks for remainders 2, 3 and 2 on division by 3, 5 and 7. Their product is 105; the partial products are 35, 21 and 15, whose respective inverses are 2, 1 and 1.
2·35·2 + 3·21·1 + 2·15·1
= 140 + 63 + 30 = 233
233 mod 105 = 23
x = 23 + 105k, k ∈ ℤ
Substitution gives 23 mod 3=2, 23 mod 5=3 and 23 mod 7=2. Successive merging first obtains 8 modulo 15, then 23 modulo 105: two constructions of the same exact class.
A certificate of impossibility
The rows x≡1 (mod 4) and x≡2 (mod 6) require odd and even parity respectively. Their GCD is 2, but the residues reduce to 1 and 0 modulo 2. This single pair proves that the whole system has no solution. Incompatibility is proved, not assumed: exhibiting one pair whose residues differ modulo their GCD is enough.
The compatibility condition and the two-modulus construction are proved in Clive Newstead, §3.3, theorems 3.3.44–45. Successive merges extend this to a finite system.
Normalization and redundancy
−1 modulo 4 and 3 modulo 4 describe the same class. Normalization places a residue between 0 and n−1 while preserving the constraint. Identical normalized rows are duplicates. Redundancy can also be collective: rows modulo 2 and 3 may imply a row modulo 6, even though neither implies it alone.
A redundant row can be removed while keeping the others. Removing every flagged row together requires checking the system again, because the flagged rows may imply one another.
Scope: one unknown, integer moduli
The case treated here has one unknown and rows x≡aᵢ (mod nᵢ), with integer moduli of at least 2. A row with a coefficient, such as 3x≡6 (mod 9), first requires solving a linear congruence and can produce several classes. Systems with coefficients, polynomials, errors in residues or multiple unknowns answer to different existence conditions. Garner, residue arithmetic and cryptographic protocols are algorithms and applications built on this theorem, not instances of it.