The site's seventh Number Theory entry. Every prior entry in this category answers a question about a single number — is it prime, what's its inverse, what's the gcd of two of them. This one answers a question about a system: given several remainders after dividing by several different moduli, what's the one number (up to the product of the moduli) that produces all of them at once? The name comes from its oldest known appearance, a puzzle in the 3rd–5th century CE Chinese text Sunzi Suanjing: "there are things of an unknown number; counted in threes, 2 remain; counted in fives, 3 remain; counted in sevens, 2 remain — how many things?" (The answer is below, in Try it.)
The combining step reuses Extended Euclidean Algorithm directly — not the plain gcd, the version that hands back Bézout coefficients — rather than introducing new machinery. That's the whole trick: two congruences merge into one via one extended-gcd call, so n congruences merge pairwise, left to right, into a single answer.
Enter matching lists of remainders and moduli (same length, comma-separated) and step through the pairwise merge. The Sunzi preset is the puzzle above — watch it converge to 23. The non-coprime, consistent preset shows the generalized version working even when the moduli share a factor. The inconsistent preset shows what happens when no such number exists at all — the algorithm has to say so, not guess.
Start by treating the first congruence, x ≡ r₁ (mod m₁), as the running answer. Merge in the
next one, x ≡ r₂ (mod m₂), by writing the running answer as x = r₁ + m₁·k for some
integer k, and substituting into the second congruence:
r₁ + m₁·k ≡ r₂ (mod m₂)
m₁·k ≡ (r₂ − r₁) (mod m₂)That's a single linear congruence in k, and Extended Euclidean already solves exactly this shape: run it on
(m₁, m₂) to get g = gcd(m₁, m₂) and coefficients with m₁·p + m₂·q = g.
A solution for k exists only if g divides (r₂ − r₁) — if it doesn't, the two congruences
contradict each other and there is no x satisfying both, no matter how far you search. When it does divide
evenly, k ≡ p·(r₂ − r₁)/g (mod m₂/g) gives the smallest non-negative k, and
merged remainder: r = r₁ + m₁·k, reduced into [0, lcm)
merged modulus: lcm = m₁·m₂ / gis a single congruence, x ≡ r (mod lcm), equivalent to both originals at once. Feed that
back in as the new running answer and merge the third congruence the same way, and so on — n congruences
collapse to one after n−1 merges, each merge doing exactly one Extended Euclidean call.
When every modulus is pairwise coprime — the textbook statement of the theorem — g is always 1, so the
"does g divide the difference" check always passes and the merged modulus is always the plain product
m₁·m₂, not just a shared multiple. That's the special case most treatments teach. Running the
same merge step unmodified past it, without assuming coprimality, is what makes the inconsistent-detection
and non-coprime-but-consistent cases (see the presets above) fall out for free instead of needing separate
code paths.
function extGcd(a, b) {
let oldR = a, r = b, oldS = 1, s = 0, oldT = 0, t = 1;
while (r !== 0) {
const q = Math.floor(oldR / r);
[oldR, r] = [r, oldR - q * r];
[oldS, s] = [s, oldS - q * s];
[oldT, t] = [t, oldT - q * t];
}
return { gcd: oldR, p: oldS, q: oldT }; // a·p + b·q = gcd
}
// merge x ≡ r1 (mod m1) and x ≡ r2 (mod m2); null if no solution exists
function mergeCongruences(r1, m1, r2, m2) {
const { gcd: g, p } = extGcd(m1, m2);
const diff = r2 - r1;
if (diff % g !== 0) return null;
const lcm = (m1 / g) * m2;
const modPart = m2 / g;
let k = ((diff / g) * p) % modPart;
if (k < 0) k += modPart;
let r = r1 + m1 * k;
r = ((r % lcm) + lcm) % lcm;
return { r, m: lcm };
}
function crt(remainders, moduli) {
let r = ((remainders[0] % moduli[0]) + moduli[0]) % moduli[0];
let m = moduli[0];
for (let i = 1; i < moduli.length; i++) {
const ri = ((remainders[i] % moduli[i]) + moduli[i]) % moduli[i];
const merged = mergeCongruences(r, m, ri, moduli[i]);
if (merged === null) return null; // no x satisfies every congruence
r = merged.r; m = merged.m;
}
return { r, m };
}The famous multiplicative formula — sum of r_i · M_i · (M_i⁻¹ mod m_i), where M_i = M/m_i — only
works when every modulus is pairwise coprime, and gives no warning when it isn't. That formula
computes each M_i⁻¹ mod m_i by assuming it exists, but a modular inverse only exists when gcd(M_i, m_i) = 1.
Feed it moduli that share a factor and it either throws (an inverse genuinely doesn't exist) or, worse, an
implementation that only checks gcd(a, m) = 1 loosely can silently produce a number that satisfies some of
the congruences and not others. The pairwise-merge approach above sidesteps this entirely: it never assumes
coprimality, and it explicitly reports "no solution" via the diff % g !== 0 check rather than
computing a wrong answer or throwing partway through. Verified directly: the non-coprime,
consistent preset (4 mod 6, 8 mod 10, sharing a factor of 2) merges cleanly to 28 mod 30, and the
inconsistent preset (0 mod 4, 1 mod 6, also sharing a factor of 2, but 1 − 0 = 1 isn't
divisible by that factor) correctly reports no solution instead of guessing — checked programmatically
against brute force across 20,000 randomly generated congruence sets (2–4 congruences, moduli 1–12) before
this page shipped: zero mismatches, including roughly 10,000 of those sets being genuinely inconsistent and
correctly detected as such by the diff % g !== 0 check alone.
The merged answer must be the same number regardless of which order the congruences are merged in, and that's not obvious from the code alone — it needs checking, not just assuming from the math. The theorem guarantees a unique answer mod the lcm of all moduli, so any valid merge order has to land on it, but a subtly wrong implementation (say, one that reduces k into the wrong range, or reuses a modulus from the wrong step) could easily produce an order-dependent bug that still looks correct for any one fixed order — a shape of bug this site has shipped before in a different geometry algorithm before catching it by varying input order. Checked here specifically: 5,000 random congruence sets, each merged in 3 additional random shuffles of the same congruences, comparing every shuffle's result against the first order's — zero mismatches.
This page's demo and reference implementation use ordinary JavaScript numbers, which silently lose
precision above 2^53 — real uses of this theorem often can't. RSA's CRT-based decryption shortcut
(splitting a decryption mod a 1024-bit-or-larger n into two mod its prime factors, then recombining with
exactly this algorithm) works entirely on numbers far past that range. A production implementation needs
arbitrary-precision arithmetic — BigInt in JavaScript, or a bignum library elsewhere — with every
% and multiplication in the code above swapped for its BigInt equivalent; the algorithm itself is
unchanged, only the arithmetic underneath it.
O(n log M) for n congruences, where M is the final combined modulus (the lcm of all the individual moduli, which equals their product when they're pairwise coprime). Each of the n−1 merge steps runs one Extended Euclidean call, and — same bound as that page's own Complexity section — an extended-gcd call on a pair bounded by M costs O(log M) division steps. n−1 such calls, each doing O(1) work per division step, gives O(n log M) overall: linear in the number of congruences, logarithmic in how big the answer's modulus ends up being.
This site's guide, Choosing a Number Theory Algorithm, compares this entry against the other thirteen Number Theory entries side by side.