Patterns/Part VI - Math & Discrete/Lucas' Theorem

Pattern Reference

Lucas' Theorem

"Compute large binomial coefficients modulo prime. nCr mod p using base-p digits. Digit DP and combinatorics intersection."

Loading...

Deep Dive Tutorial

Lucas 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.

Lucas theorem + modular combinations
// 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 p

Worked Problems

1
Pascal's Triangle
Easy
Solve ↗
2
Count Anagram Substrings
Hard
Solve ↗
3
Unique Paths
Medium
Solve ↗
4
Number of Dice Rolls With Target Sum
Medium
Solve ↗
chart-column
Lucas theorem formula:
C(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.
← All Patterns