Chapter 127

Chinese Remainder Theorem

CRT finds x modulo M = m₁×m₂×...×mₖ that satisfies x ≡ aᵢ (mod mᵢ) for pairwise coprime moduli. Used for working with large numbers via smaller moduli, and for reconstructing results in RSA.

CRT for Two Congruences

C++ — CRT (two equations)

pair crt(long long a1, long long m1, long long a2, long long m2) {
    // Returns {x, lcm} where x is the solution modulo lcm
    long long p, q;
    long long g = extended_gcd(m1, m2, p, q);
    if ((a2 - a1) % g != 0) return {-1, -1};  // no solution

    long long lcm = m1 / g * m2;
    long long x = a1 + m1 * ((a2 - a1) / g % (m2 / g)) * p % lcm;
    return {(x % lcm + lcm) % lcm, lcm};
}

// For multiple equations: iterate crt(crt(...), next).