The Chinese remainder theorem

Suppose m and n are coprime positive integers, both at least two, and require x congruent to a modulo m and to b modulo n. Since n is invertible modulo m, choose u with nu congruent to one modulo m. Likewise choose v with mv congruent to one modulo n. The quantity nu behaves like one in the first coordinate and zero in the second; mv does the reverse.

Multiply these selectors by the desired residues and add. Reducing the expression modulo m kills the second term and leaves a, while reduction modulo n leaves b. This constructs a solution for every pair of target residues. The construction works with negative coefficients as well as positive ones, and reducing at the end to a representative between zero and mn − 1 is a convenience rather than an extra mathematical restriction.

If x and y solve the same pair of congruences, both m and n divide x − y. Coprimality then implies mn divides x − y. Thus all solutions lie in a single class modulo mn, and every member of that class is again a solution. The theorem promises uniqueness of a residue class, not a unique integer; there are infinitely many integer representatives separated by the product.

For more than two pairwise coprime moduli, combine two constraints and then combine the result with the next. Alternatively, make one selector per modulus by multiplying all the others and inverting that product in its own coordinate. Pairwise coprimality matters: merely having no prime common to the entire list is insufficient. The moduli six, ten, and fifteen have overall gcd one but are not independent in pairs.

For arbitrary m and n let d be their gcd. Any simultaneous solution must satisfy a congruent to b modulo d, since d divides both x − a and x − b. Conversely, if d divides b − a, set x = a + mt and solve mt congruent to b − a modulo n. If n/d = 1, the second constraint is automatic once compatibility holds. Otherwise division by d produces an invertible coefficient modulo n/d. Thus the compatibility condition is sufficient in both cases.

In this general case the solution class has period lcm(m, n), not necessarily mn. The product can overcount the same information because both moduli contain a shared constraint. This perspective is useful for periodic schedules, reconstruction from residues, and splitting computations into smaller pieces. Reconstruction does not magically recover an unbounded unknown integer: a range bound or a chosen class is still needed to turn the modular answer into a single measured value.