Pattern Guide
Lucas Theorem & Combinatorics Mod p
"C(n,k) mod prime p in O(log_p n). Pascal mod p has fractal structure."
Lucas theorem computes C(n,k) mod prime p in O(log_p n) by decomposing n and k in base p. Combined with precomputed factorials mod p, this solves: C(n,k) mod prime for huge n,k; counting lattice paths with prime modulus; and binomial sums. For prime powers (not just primes), use Andrew Granville's generalization or Lucas-Granville. Essential for counting problems in competitive programming.
Problems you can solve with this pattern
4 problems · click any to start solving
// Modular arithmetic setup
function modCombinatorics(MOD) { // MOD must be prime
const fact = new Array(MOD).fill(1n);
const inv = new Array(MOD).fill(1n);
const M = BigInt(MOD);
for (let i = 1; i < MOD; i++) fact[i] = fact[i-1] * BigInt(i) % M;
// Fermat's little theorem: a^(-1) ≡ a^(p-2) mod p
const pow = (b, e, m) => { let r = 1n; b %= m; while (e > 0n) { if (e & 1n) r = r*b%m; b = b*b%m; e >>= 1n; } return r; };
inv[MOD - 1] = pow(fact[MOD - 1], M - 2n, M);
for (let i = MOD - 2; i >= 1; i--) inv[i] = inv[i + 1] * BigInt(i + 1) % M;
const C = (n, k) => {
if (k < 0 || k > n) return 0n;
return fact[n] * inv[k] % M * inv[n - k] % M;
};
// Lucas theorem: C(n, k) mod p for large n, k
const lucas = (n, k) => {
if (k === 0n) return 1n;
const [ni, ki] = [n % M, k % M];
return C(Number(ni), Number(ki)) * lucas(n / M, k / M) % M;
};
return { C, lucas, fact, inv };
}
// Example: C(10^18, 10^9) mod 1000000007
// const { lucas } = modCombinatorics(1e9 + 7);
// lucas(BigInt(1e18), BigInt(1e9))
// Wilson's theorem: (p-1)! ≡ -1 (mod p) for prime p
// Fermat's little theorem: a^p ≡ a (mod p) for prime p
// a^(p-1) ≡ 1 (mod p) for a not divisible by pLucas theorem: C(n,k) mod p = Π C(nᵢ, kᵢ) mod p, where nᵢ, kᵢ are digits of n, k in base p. If any kᵢ > nᵢ, result is 0. Precompute factorials and inverse factorials up to p using Fermat's little theorem (a^(p-2) ≡ a^(-1) mod p). For large n (up to 10^18) and prime p (up to 10^6): Lucas gives O(p + log_p(n)) complexity.
// Modular arithmetic setup
function modCombinatorics(MOD) { // MOD must be prime
const fact = new Array(MOD).fill(1n);
const inv = new Array(MOD).fill(1n);
const M = BigInt(MOD);
for (let i = 1; i < MOD; i++) fact[i] = fact[i-1] * BigInt(i) % M;
// Fermat's little theorem: a^(-1) ≡ a^(p-2) mod p
const pow = (b, e, m) => { let r = 1n; b %= m; while (e > 0n) { if (e & 1n) r = r*b%m; b = b*b%m; e >>= 1n; } return r; };
inv[MOD - 1] = pow(fact[MOD - 1], M - 2n, M);
for (let i = MOD - 2; i >= 1; i--) inv[i] = inv[i + 1] * BigInt(i + 1) % M;
const C = (n, k) => {
if (k < 0 || k > n) return 0n;
return fact[n] * inv[k] % M * inv[n - k] % M;
};
// Lucas theorem: C(n, k) mod p for large n, k
const lucas = (n, k) => {
if (k === 0n) return 1n;
const [ni, ki] = [n % M, k % M];
return C(Number(ni), Number(ki)) * lucas(n / M, k / M) % M;
};
return { C, lucas, fact, inv };
}
// Example: C(10^18, 10^9) mod 1000000007
// const { lucas } = modCombinatorics(1e9 + 7);
// lucas(BigInt(1e18), BigInt(1e9))
// Wilson's theorem: (p-1)! ≡ -1 (mod p) for prime p
// Fermat's little theorem: a^p ≡ a (mod p) for prime p
// a^(p-1) ≡ 1 (mod p) for a not divisible by pC(n, k) ≡ Π C(nᵢ, kᵢ) (mod p), where n = Σ nᵢpⁱ, k = Σ kᵢpⁱ in base p.
Applications:
- C(n, k) mod prime for n,k up to 10^18
- Counting lattice paths modulo prime
- Binomial coefficient parity (p=2 version is just digit-AND check)
Kummer's theorem: The highest power of prime p dividing C(n,k) = number of carries when adding k and n-k in base p.
Vandermonde's identity: C(m+n, r) = Σ C(m,i)×C(n,r-i). Useful for proving counting identities.
Fermat's little theorem: a^(p-1) ≡ 1 mod p → modular inverse of a = a^(p-2) mod p.