Lucas's Theorem

Combinations Modulo a Prime

Calculating binomial coefficients, $\binom{n}{k}$ , is straightforward when $n$ and $k$ are small. However, in competitive programming and number theory, $n$ and $k$ can be enormous, often up to $10^{18}$ , while the modulus $p$ is a relatively small prime. The standard formula $\frac{n!}{k!(n-k)!}$ becomes computationally infeasible. We can't compute the factorials directly due to their size, and modular division requires modular inverses, which rely on Fermat's Little Theorem or the Extended Euclidean Algorithm. Precomputing factorials up to $n$ is also out of the question due to memory and time constraints.

This is where Lucas's Theorem provides an elegant and efficient solution. It breaks down the computation of a single large binomial coefficient modulo $p$ into a product of several smaller ones that are manageable to compute.

Lucas's Theorem

The theorem states that for a prime $p$ and non-negative integers $n$ and $k$ , a specific congruence relationship holds. To apply it, we first need to express $n$ and $k$ in base $p$ (their p-adic representations).

\binom{n}{k} \equiv \prod_{i=0}^{m} \binom{n_i}{k_i} \pmod{p}

This decomposition is powerful. The values $n_i$ and $k_i$ are simply the digits of $n$ and $k$ in base $p$ , so they are always less than $p$ . This reduces the problem of one massive combination to several small combinations where the arguments are less than $p$ .

Consider $\binom{28}{11} \pmod{5}$ . First, we find the base-5 representations: $28 = 1 \cdot 5^2 + 0 \cdot 5^1 + 3 \cdot 5^0 \implies n = (103)_5$ $11 = 0 \cdot 5^2 + 2 \cdot 5^1 + 1 \cdot 5^0 \implies k = (021)_5$

Applying Lucas's Theorem: $\binom{28}{11} \equiv \binom{1}{0} \binom{0}{2} \binom{3}{1} \pmod{5}$ Since $\binom{0}{2} = 0$ , the entire product is 0. So, $\binom{28}{11} \equiv 0 \pmod{5}$ .

Implementation Strategy

To implement Lucas's Theorem for competitive programming, we need an efficient way to calculate $\binom{n_i}{k_i} \pmod{p}$ for $n_i, k_i < p$ . Since $p$ is prime, we can precompute factorials and their modular multiplicative inverses up to $p-1$ . The binomial coefficient can then be found using the formula:

$\binom{n}{k} = n! \cdot (k!)^{-1} \cdot ((n-k)! )^{-1} \pmod{p}$

This makes each small combination calculation an $O(1)$ lookup after an initial $O(p)$ precomputation step.

The overall algorithm is as follows:

Precomputation: Calculate fact[i] for $i$ from $0$ to $p-1$ . Calculate modular inverses for these factorials. This takes $O(p)$ time.
Query: To compute $\binom{n}{k} \pmod{p}$ , iterate while $n > 0$ or $k > 0$ . In each step, get the last base- $p$ digits: $n_i = n \% p$ and $k_i = k \% p$ . Calculate $\binom{n_i}{k_i} \pmod{p}$ using the precomputed values. Multiply this into a running product. Then, update $n$ and $k$ by integer division: $n = n / p$ and $k = k / p$ . This process extracts the digits from right to left.

The query step's complexity is determined by the number of digits in the base- $p$ representation of $n$ , which is $O(\log_p n)$ . The total complexity is dominated by the precomputation, giving us $O(p + \log_p n)$ per query.

#include <iostream>
#include <vector>

// Computes (base^exp) % mod
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// Computes modular inverse of n under mod
long long modInverse(long long n, long long mod) {
    return power(n, mod - 2, mod);
}

// Computes nCr % p using precomputed factorials
long long nCr_mod_p(int n, int r, const std::vector<long long>& fact, const std::vector<long long>& invFact, long long p) {
    if (r < 0 || r > n) {
        return 0;
    }
    return (((fact[n] * invFact[r]) % p) * invFact[n - r]) % p;
}

// Main function to compute C(n, k) % p using Lucas's Theorem
long long lucas(long long n, long long k, long long p) {
    if (k < 0 || k > n) {
        return 0;
    }
    if (p == 0) return 0; // Invalid modulus

    // Precomputation step
    std::vector<long long> fact(p);
    std::vector<long long> invFact(p);
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i < p; ++i) {
        fact[i] = (fact[i - 1] * i) % p;
        invFact[i] = modInverse(fact[i], p);
    }

    // Query step
    long long result = 1;
    while (n > 0 || k > 0) {
        long long ni = n % p;
        long long ki = k % p;
        result = (result * nCr_mod_p(ni, ki, fact, invFact, p)) % p;
        n /= p;
        k /= p;
    }
    return result;
}

int main() {
    long long n = 28, k = 11, p = 5;
    std::cout << "C(" << n << ", " << k << ") mod " << p << " is " << lucas(n, k, p) << std::endl; // Output: 0

    n = 100, k = 30, p = 13;
    std::cout << "C(" << n << ", " << k << ") mod " << p << " is " << lucas(n, k, p) << std::endl; // Output: 5

    return 0;
}

This implementation structure is highly effective for problems where you need to answer multiple queries for $\binom{n}{k} \pmod{p}$ with the same prime $p$ . The precomputation can be done once, making subsequent queries very fast.

Connection to Pascal's Triangle

Lucas's Theorem provides a deep insight into the structure of Pascal's Triangle modulo a prime $p$ . When you color the entries of Pascal's Triangle based on their value modulo $p$ (e.g., color entries divisible by $p$ black and others white), a distinct fractal pattern emerges. This pattern is the Sierpiński triangle for $p=2$ .

The theorem explains this self-similarity. The condition that $\binom{n}{k} \equiv 0 \pmod{p}$ if any base- $p$ digit $k_i$ is greater than $n_i$ creates large triangular regions of zeros in the overall pattern. The pattern of non-zero values within the first $p$ rows then repeats at different scales throughout the triangle, governed by the base- $p$ representation of the row and column numbers.

Quiz Questions 1/6

What is the primary computational challenge that Lucas's Theorem is designed to solve efficiently?

Quiz Questions 2/6

According to Lucas's Theorem, to compute ${\binom{n}{k}} \pmod{p}$ , the problem is broken down by first representing $n$ and $k$ in which base?

Lucas's Theorem is a cornerstone technique for handling large combinatorial calculations in modular arithmetic, essential for advanced algorithm design and number theory problems.

Advanced Combinatorics and Pascal's Analytic Properties

Advanced Combinatorics and Pascal's Analytic Properties

Lucas's Theorem

Combinations Modulo a Prime

Lucas's Theorem

Implementation Strategy

Connection to Pascal's Triangle