Chinese Remainder Theorem — Combining Congruences

Construction

long crt(long[] a, long[] n) {
  long N = 1;
  for (long ni : n) N *= ni;
  long result = 0;
  for (int i = 0; i < a.length; i++) {
    long Ni = N / n[i];
    long Mi = modInverse(Ni, n[i]);
    result = (result + a[i] * Ni * Mi) % N;
  }
  return result;
}

Non-coprime CRT

Merge congruences pairwise via extended Euclidean. Check compatibility (a₁ ≡ a₂ mod gcd(n₁, n₂)).

Applications

RSA signature. Fast polynomial multiplication via multiple primes. Distributed computation.

Speed up

Compute mod many small primes → combine. Avoids big-integer arithmetic in intermediate steps.