Pattern Guide
Chinese Remainder Theorem
"Solve x ≡ a1 (mod m1), x ≡ a2 (mod m2), ... in one shot. Extended Euclidean key."
Chinese Remainder Theorem (CRT) finds x such that x ≡ aᵢ (mod mᵢ) for all i, when mᵢ are pairwise coprime. Extended to non-coprime moduli using extended Euclidean algorithm. Applications: combining multiple modular constraints, computing large numbers modulo several primes, calendar problems, and number theory competition problems.
14 min readmath problems →
Problems you can solve with this pattern
4 problems · click any to start solving
Extended Euclidean, modular inverse, and CRT
// Extended Euclidean: returns [g, x, y] where ax + by = g = gcd(a, b)
function extGcd(a, b) {
if (!b) return [a, 1, 0];
const [g, x, y] = extGcd(b, a % b);
return [g, y, x - Math.floor(a / b) * y];
}
// Modular inverse of a mod m (requires gcd(a,m) = 1)
function modInv(a, m) {
const [g, x] = extGcd(a % m, m);
if (g !== 1) return -1; // no inverse
return ((x % m) + m) % m;
}
// CRT for coprime moduli: solve x ≡ a (mod m) and x ≡ b (mod n)
function crtCoprime(a, m, b, n) {
// x = a + m * (b - a) * modInv(m, n) mod (m*n)
const t = ((BigInt(b) - BigInt(a)) % BigInt(n) + BigInt(n)) % BigInt(n);
const inv = BigInt(modInv(Number(BigInt(m) % BigInt(n)), Number(n)));
const x = BigInt(a) + BigInt(m) * (t * inv % BigInt(n));
return [Number(x % (BigInt(m) * BigInt(n))), m * n];
}
// General CRT (handles non-coprime moduli)
// Returns [x, lcm] or [-1, -1] if no solution
function crtGeneral(a, m, b, n) {
// x ≡ a (mod m), x ≡ b (mod n)
const [g, p] = extGcd(m, n);
if ((b - a) % g !== 0) return [-1, -1]; // no solution
const lcm = m / g * n;
const x = ((a + m * ((b - a) / g * p % (n / g))) % lcm + lcm) % lcm;
return [x, lcm];
}
// Solve system of congruences: x ≡ rems[i] (mod mods[i])
function solveCRT(rems, mods) {
let [r, m] = [rems[0], mods[0]];
for (let i = 1; i < rems.length; i++) {
[r, m] = crtGeneral(r, m, rems[i], mods[i]);
if (r === -1) return -1; // no solution
}
return r;
}CRT states: if m₁, m₂, ..., mₖ are pairwise coprime, then for any a₁, a₂, ..., aₖ there exists a unique x (mod M = m₁m₂...mₖ) satisfying all congruences. Construction: x = Σ aᵢ · Mᵢ · (Mᵢ⁻¹ mod mᵢ), where Mᵢ = M/mᵢ. For non-coprime moduli, use the "combine two at a time" method with extended Euclidean.
Extended Euclidean, modular inverse, and CRT
// Extended Euclidean: returns [g, x, y] where ax + by = g = gcd(a, b)
function extGcd(a, b) {
if (!b) return [a, 1, 0];
const [g, x, y] = extGcd(b, a % b);
return [g, y, x - Math.floor(a / b) * y];
}
// Modular inverse of a mod m (requires gcd(a,m) = 1)
function modInv(a, m) {
const [g, x] = extGcd(a % m, m);
if (g !== 1) return -1; // no inverse
return ((x % m) + m) % m;
}
// CRT for coprime moduli: solve x ≡ a (mod m) and x ≡ b (mod n)
function crtCoprime(a, m, b, n) {
// x = a + m * (b - a) * modInv(m, n) mod (m*n)
const t = ((BigInt(b) - BigInt(a)) % BigInt(n) + BigInt(n)) % BigInt(n);
const inv = BigInt(modInv(Number(BigInt(m) % BigInt(n)), Number(n)));
const x = BigInt(a) + BigInt(m) * (t * inv % BigInt(n));
return [Number(x % (BigInt(m) * BigInt(n))), m * n];
}
// General CRT (handles non-coprime moduli)
// Returns [x, lcm] or [-1, -1] if no solution
function crtGeneral(a, m, b, n) {
// x ≡ a (mod m), x ≡ b (mod n)
const [g, p] = extGcd(m, n);
if ((b - a) % g !== 0) return [-1, -1]; // no solution
const lcm = m / g * n;
const x = ((a + m * ((b - a) / g * p % (n / g))) % lcm + lcm) % lcm;
return [x, lcm];
}
// Solve system of congruences: x ≡ rems[i] (mod mods[i])
function solveCRT(rems, mods) {
let [r, m] = [rems[0], mods[0]];
for (let i = 1; i < rems.length; i++) {
[r, m] = crtGeneral(r, m, rems[i], mods[i]);
if (r === -1) return -1; // no solution
}
return r;
}CRT use cases:
- Multiple modular constraints: find x satisfying all at once
- Large number reconstruction from remainders (secret sharing)
- Counting problems where answer must be computed mod several primes for verification
Extended Euclidean: Computes gcd(a,b) and coefficients x,y with ax+by=gcd. The modular inverse of a mod m is x from extGcd(a,m) when gcd=1.
General CRT (non-coprime mods): Combine two constraints at a time using extGcd. If (b-a) % gcd(m,n) ≠ 0, no solution exists.
Fast modular exponentiation: Always use BigInt in JavaScript for large exponents to avoid precision issues.
- Multiple modular constraints: find x satisfying all at once
- Large number reconstruction from remainders (secret sharing)
- Counting problems where answer must be computed mod several primes for verification
Extended Euclidean: Computes gcd(a,b) and coefficients x,y with ax+by=gcd. The modular inverse of a mod m is x from extGcd(a,m) when gcd=1.
General CRT (non-coprime mods): Combine two constraints at a time using extGcd. If (b-a) % gcd(m,n) ≠ 0, no solution exists.
Fast modular exponentiation: Always use BigInt in JavaScript for large exponents to avoid precision issues.