Lucas' Theorem — Binomial Coefficient mod Prime

Statement

Write n = sum nᵢ · p^i, k = sum kᵢ · p^i. C(n, k) ≡ ∏ C(nᵢ, kᵢ) (mod p).

Algorithm

long lucas(long n, long k, long p) {
  long result = 1;
  while (n > 0 || k > 0) {
    long ni = n % p, ki = k % p;
    if (ki > ni) return 0;
    result = result * binomialModP(ni, ki, p) % p;
    n /= p; k /= p;
  }
  return result;
}

Complexity

O(log_p(n)) iterations. Each computes small binomial mod p.

Composite mod

CRT: split into prime powers. Wilson + Granville for prime powers. General but complex.