Chinese Remainder Theorem

// 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;
}