Back to Number Theory Dsa

Modular Combinatorics

September 22, 2026 Wasil Zafar 10 min read

Evaluate combinatorial quantities under prime and composite moduli.

Table of Contents

  1. Intuition, Vocabulary and Foundations
  2. Step-by-Step Derivations and Algorithms
  3. Implementation, Complexity and Engineering
  4. Applications, Case Studies and Exercises

Intuition, Vocabulary and Foundations

A binomial coefficient counts selections: $\binom{n}{k}$ is the number of ways to choose $k$ objects from $n$ without order. For example, choosing a three-person team from five people gives $\binom{5}{3}=10$. Factorials express this count as

$$ \binom{n}{k}=\frac{n!}{k!(n-k)!}, \qquad n!=1\cdot2\cdots n, \qquad 0!=1. $$

This integer formula becomes subtle under a modulus. Division modulo $m$ means multiplication by an inverse, and $a$ has an inverse modulo $m$ exactly when $\gcd(a,m)=1$. Thus factorial inverses work modulo a prime $p$ only while the factorials being inverted are nonzero modulo $p$.

The $p$-adic valuation $v_p(x)$ counts the copies of $p$ in $x$. Legendre's formula gives

$$ v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor, \qquad v_p\!\left(\binom{n}{k}\right)=v_p(n!)-v_p(k!)-v_p((n-k)!). $$

For a prime $p$, Lucas's theorem writes $n=\sum_i n_ip^i$ and $k=\sum_i k_ip^i$, then states

$$ \binom{n}{k}\equiv\prod_i\binom{n_i}{k_i}\pmod p. $$

If some $k_i\gt n_i$, the result is zero. For a composite modulus, factor it into pairwise coprime prime powers, compute one residue per prime power while preserving its valuation, and reconstruct the unique result with the Chinese Remainder Theorem.

Modular division is valid only for invertible denominators. Before using factorial inverses, prove the denominator is coprime to the modulus; otherwise separate its prime-power valuation, compute the invertible unit part, and reconstruct with CRT.

ConceptDefinition or notationExampleBoundary or non-exampleQuestion answered
Factorial$n!=\prod_{i=1}^{n}i$ and $0!=1$$5!=120$Negative factorials are outside this modelHow many ordered arrangements exist?
Binomial coefficient$\binom{n}{k}=n!/(k!(n-k)!)$$\binom{5}{2}=10$$\binom{5}{7}=0$ by conventionHow many unordered selections exist?
Multinomial coefficient$\binom{n}{k_1,\ldots,k_r}=n!/\prod_i k_i!$$\binom{5}{2,2,1}=30$Requires $\sum_i k_i=n$How many labeled groupings exist?
Modular inverse$aa^{-1}\equiv1\pmod m$$3^{-1}\equiv5\pmod7$$2$ has no inverse modulo $6$Is division by $a$ legal?
Valuation$v_p(x)$ is the exponent of $p$ in $x$$v_2(40)=3$$v_p(0)$ is not finiteHow much of $p$ divides a value?
Lucas theoremBase-$p$ digit product modulo prime $p$$\binom{10}{3}\equiv0\pmod5$It requires prime $p$How can huge indices be handled?
Prime-power methodTrack $p$ separately from unit factors$\binom{6}{2}\equiv7\pmod8$Ordinary factorial inverses modulo $8$ failHow are nonunits retained?
CRT reconstructionMerge residues for coprime moduliResidues modulo $8$ and $5$ merge modulo $40$Coprimality must be establishedHow are component answers combined?

Step-by-Step Derivations and Algorithms

For repeated queries with $0\le n\lt p$, precompute $F[i]\equiv i!\pmod p$. Fermat's little theorem gives $F[N]^{-1}\equiv F[N]^{p-2}\pmod p$, and a backward pass uses $F^{-1}[i-1]\equiv iF^{-1}[i]\pmod p$. Each query then takes $O(1)$ time:

$$ \binom{n}{k}\equiv F[n]F^{-1}[k]F^{-1}[n-k]\pmod p. $$

The proof obligation is $N\lt p$, because otherwise a stored factorial may be zero and noninvertible modulo $p$. When $n$ is much larger than a small prime $p$, Lucas repeatedly extracts $n_i=n\bmod p$ and $k_i=k\bmod p$, multiplies $\binom{n_i}{k_i}$, and divides both indices by $p$.

For $P=p^q$, write $\binom{n}{k}=p^e u$, where $u$ is coprime to $p$. If $e\ge q$, the residue is zero modulo $P$. Otherwise, compute factorial unit parts with factors of $p$ removed, divide those units using modular inverses, and restore $p^e$.

For a composite modulus $m=\prod_j p_j^{q_j}$, solve independently modulo each prime power. To merge $x\equiv a\pmod M$ and $x\equiv b\pmod P$, solve $Mt\equiv b-a\pmod P$, then update $a\leftarrow a+Mt$ and $M\leftarrow MP$.

Modular Combinatorics algorithm map
flowchart TD
    A["Read n, k, and modulus m"] --> B{"Is m prime?"}
    B -->|"Yes"| C{"Are all n below m?"}
    C -->|"Yes"| D["Factorial and inverse tables"]
    C -->|"No"| E["Lucas base-m digits"]
    B -->|"No"| F["Factor m into prime powers"]
    F --> G["Track valuations and unit parts"]
    G --> H["Residue for each prime power"]
    H --> I["CRT reconstruction"]
    D --> J["Return coefficient"]
    E --> J
    I --> J

The invariant is that every removed factor of $p$ is counted in the valuation while every remaining unit is invertible modulo $p^q$. Prime-table queries take $O(1)$ after $O(N)$ preprocessing, Lucas takes $O(\log_p n)$ per query after $O(p)$ preprocessing, and composite moduli add prime-power evaluation plus CRT reconstruction.

Implementation, Complexity and Engineering

The implementation provides two dependable reference modes. PrimeBinomial serves many queries with $n\lt p$, while binomial_mod computes the exact integer coefficient before reducing modulo any positive modulus. The latter is intentionally a modest-input oracle for validating optimized prime-power code.

Multinomial coefficients reuse the same engine through

$$ \binom{n}{k_1,\ldots,k_r} =\binom{n}{k_1}\binom{n-k_1}{k_2}\cdots. $$

from math import gcd


def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    divisor = 3
    while divisor <= n // divisor:
        if n % divisor == 0:
            return False
        divisor += 2
    return True


def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    if b == 0:
        return abs(a), 1 if a >= 0 else -1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def modular_inverse(value: int, modulus: int) -> int:
    if modulus <= 1:
        raise ValueError("modulus must exceed 1")
    g, x, _ = extended_gcd(value, modulus)
    if g != 1:
        raise ValueError("value is not invertible modulo modulus")
    return x % modulus


class PrimeBinomial:
    """O(N) preparation and O(1) queries for 0 <= n <= N < prime."""

    def __init__(self, maximum: int, prime: int):
        if maximum < 0:
            raise ValueError("maximum must be nonnegative")
        if not is_prime(prime):
            raise ValueError("modulus must be prime")
        if maximum >= prime:
            raise ValueError("factorial table requires maximum < prime")
        self.maximum = maximum
        self.prime = prime
        self.factorial = [1] * (maximum + 1)
        for i in range(1, maximum + 1):
            self.factorial[i] = self.factorial[i - 1] * i % prime
        self.inverse_factorial = [1] * (maximum + 1)
        self.inverse_factorial[maximum] = pow(
            self.factorial[maximum], prime - 2, prime
        )
        for i in range(maximum, 0, -1):
            self.inverse_factorial[i - 1] = (
                self.inverse_factorial[i] * i
            ) % prime

    def choose(self, n: int, k: int) -> int:
        if n < 0:
            raise ValueError("n must be nonnegative")
        if k < 0 or k > n:
            return 0
        if n > self.maximum:
            raise ValueError("query exceeds the prepared range")
        return (
            self.factorial[n]
            * self.inverse_factorial[k]
            * self.inverse_factorial[n - k]
        ) % self.prime


def lucas_binomial(n: int, k: int, prime: int) -> int:
    if n < 0:
        raise ValueError("n must be nonnegative")
    if k < 0 or k > n:
        return 0
    table = PrimeBinomial(prime - 1, prime)
    result = 1
    while n or k:
        n_digit, k_digit = n % prime, k % prime
        if k_digit > n_digit:
            return 0
        result = result * table.choose(n_digit, k_digit) % prime
        n //= prime
        k //= prime
    return result


def exact_binomial(n: int, k: int) -> int:
    if n < 0:
        raise ValueError("n must be nonnegative")
    if k < 0 or k > n:
        return 0
    k = min(k, n - k)
    result = 1
    for i in range(1, k + 1):
        result = result * (n - k + i) // i
    return result


def binomial_mod(n: int, k: int, modulus: int) -> int:
    if modulus <= 0:
        raise ValueError("modulus must be positive")
    if modulus == 1:
        return 0
    return exact_binomial(n, k) % modulus


def multinomial_mod(parts: list[int], modulus: int) -> int:
    if modulus <= 0:
        raise ValueError("modulus must be positive")
    if any(part < 0 for part in parts):
        raise ValueError("part sizes must be nonnegative")
    remaining = sum(parts)
    result = 1 % modulus
    for part in parts:
        result = result * binomial_mod(remaining, part, modulus) % modulus
        remaining -= part
    return result


def merge_coprime_congruences(
    residues: list[int], moduli: list[int]
) -> tuple[int, int]:
    if len(residues) != len(moduli) or not residues:
        raise ValueError("provide equally sized nonempty lists")
    answer, combined = 0, 1
    for residue, modulus in zip(residues, moduli):
        if modulus <= 1:
            raise ValueError("each modulus must exceed 1")
        if gcd(combined, modulus) != 1:
            raise ValueError("moduli must be pairwise coprime")
        step = ((residue - answer) * modular_inverse(combined, modulus)) % modulus
        answer += combined * step
        combined *= modulus
        answer %= combined
    return answer, combined


if __name__ == "__main__":
    table = PrimeBinomial(20, 1_000_000_007)
    assert table.choose(5, 2) == 10
    assert table.choose(8, 0) == 1
    assert table.choose(8, 9) == 0
    assert lucas_binomial(10, 3, 5) == 0
    assert lucas_binomial(100, 20, 7) == exact_binomial(100, 20) % 7
    assert binomial_mod(6, 2, 8) == 7
    assert binomial_mod(20, 10, 1) == 0
    assert multinomial_mod([2, 2, 1], 1_000) == 30
    residue, modulus = merge_coprime_congruences([7, 0], [8, 5])
    assert (residue, modulus) == (15, 40)
    assert residue == binomial_mod(6, 2, 40)
    try:
        modular_inverse(2, 6)
        raise AssertionError("noninvertible value was accepted")
    except ValueError:
        pass
    print("all tests passed")
MethodPreparationPer-query costSuitable regimeFailure modeMitigation
Pascal recurrence$O(N^2)$ time and storage$O(1)$ lookupSmall $N$, arbitrary modulusQuadratic memoryKeep rolling rows when history is unnecessary
Prime factorial tables$O(N)$ time and storage$O(1)$Many queries with $N\lt p$Inverting zero when $N\ge p$Enforce $N\lt p$ at construction
Exact multiplicative formulaNone$O(\min(k,n-k))$ big-integer stepsModest inputs and testingLarge intermediatesCancel at every step and exploit symmetry
Lucas theorem$O(p)$$O(\log_p n)$Huge $n$, small prime modulusComposite modulusValidate primality first
Prime-power methodBlock-dependentLogarithmic recursion plus modular workComposite moduliLosing removed factors of $p$Track valuations separately
CRT reconstructionFactorization-dependent$O(t\log m)$ for $t$ factorsCoprime prime-power factorsProduct overflowUse big integers or checked multiplication
Multinomial by binomialsReuses binomial engine$O(r)$ queriesPrescribed group sizesInvalid or negative partsValidate parts and remaining total

Applications, Case Studies and Exercises

A query engine should select its strategy from the modulus, maximum $n$, and query volume. Millions of bounded queries modulo one large prime favor factorial tables. Huge indices with a small prime favor Lucas. Composite moduli require prime-power decomposition whenever denominator factors may be noninvertible.

Multinomial queries arise in inventory allocation, categorical sequences, and contingency tables. Reduce them to a product of binomial coefficients and route each factor through the same modulus-aware strategy.

Practice

Apply Modular Combinatorics

Case study 1 — repeated team selections. A tournament service asks $10^6$ queries of the form $\binom{n}{k}\bmod 1{,}000{,}000{,}007$, with $0\le n\le10^6$. Precompute factorial and inverse-factorial tables. Check that $\binom{5}{2}=10$, $\binom{n}{0}=\binom{n}{n}=1$, and $\binom{n}{k}=\binom{n}{n-k}$. Success means $O(1)$ query time and agreement with Pascal's recurrence for every $n\le100$.

Case study 2 — composite-modulus analytics. Compute $\binom{n}{k}\bmod360$, where $360=8\cdot9\cdot5$. Preserve valuations while computing modulo $2^3$, $3^2$, and $5$, then merge with CRT. For $\binom{6}{2}=15$, the component residues must be $7$, $6$, and $0$, and reconstruction must return $15\bmod360$.

Hands-on engine. Accept a modulus, maximum input, query count, and binomial or multinomial request. Select factorial tables, Lucas, a prime-power method, or the exact oracle. Measure preparation time, latency, and memory. Success requires matching exact arithmetic on $10{,}000$ randomized cases with $0\le n\le200$ and moduli including $1$, primes, prime powers, and mixed composites.

Tiered exercises. (1) Compute $\binom{8}{3}$ modulo $5$, $7$, and $8$. (2) Use Legendre's formula to find $v_2\!\left(\binom{20}{6}\right)$. (3) Evaluate $\binom{100}{20}\bmod7$ with Lucas. (4) Add batched multinomial queries. (5) Explain why factorial inverses fail when $n\ge p$. (6) Implement the prime-power method and combine its residues with CRT.

Use factorial tables for dense bounded prime-modulus queries, Lucas for huge indices under a small prime, and valuation-aware prime-power arithmetic plus CRT for composite moduli. The central misconception is treating modular division like integer division: every inverse must be justified.

Next in the Series

In Diophantine Equations & Continued Fractions, we'll explore Use constructive integer methods for equations and best approximations..

Continue the Series

Linear Congruences & Chinese Remainder Theorem

Solve one or many compatible modular constraints.

Read Article
Arithmetic Functions, Convolution & Möbius Inversion

Exploit multiplicativity and convolution to transform counting problems.

Read Article