Lucas's theorem

Lucas's theorem is a result in combinatorial number theory that provides an efficient method for computing the binomial coefficient \binom{n}{m} modulo a prime number p, by expressing n and m in their base-p expansions and taking the product of the corresponding smaller binomial coefficients modulo p.^[1] Formulated by the French mathematician Édouard Lucas in 1878, the theorem builds on earlier work in modular arithmetic and binomial coefficients by figures such as Charles Babbage, Joseph Wolstenholme, and Ernst Kummer.^[1] Specifically, if n = \sum_{i=0}^k n_i p^i and m = \sum_{i=0}^k m_i p^i where $0 \leq n_i, m_i < p, then \binom{n}{m} \equiv \prod_{i=0}^k \binom{n_i}{m_i} \pmod{p}, with the understanding that \binom{n_i}{m_i} = 0 if m_i > n_i for any i.^[1] This criterion simplifies calculations for large n and m, revealing patterns such as the fractal structure of Pascal's triangle modulo p.^[2] Beyond its core statement, Lucas's theorem has spurred numerous generalizations, including extensions to prime powers and q-analogues, as developed by mathematicians like Andrew Granville and others in the late 20th and early 21st centuries, with recent reformulations continuing as of 2025.^[1]^[3] Its applications span number theory, where it aids in studying divisibility properties and primality testing, and combinatorics, facilitating analysis of generating functions and algebraic identities.^[1] The theorem's elegance and utility continue to influence research in modular forms and computational mathematics.^[1]

Overview

Statement

Lucas's theorem provides a criterion for determining the value of a binomial coefficient modulo a prime number p.^[4]^[5] The binomial coefficient \binom{m}{n} for non-negative integers m and n with m \geq n is defined as \frac{m!}{n!(m-n)!}, and it equals 0 otherwise; here, the factorial k! denotes the product of all positive integers up to k.^[5] Modular arithmetic involves congruences of the form a \equiv b \pmod{p}, meaning p divides a - b.^[5] To apply the theorem, express the non-negative integers m and n in base p as

m = m_k p^k + \cdots + m_1 p + m_0, \quad n = n_k p^k + \cdots + n_1 p + n_0,

where $0 \leq m_i, n_i < p for each i = 0, 1, \dots, k, and higher digits are zero.^[4]^[5] The theorem states that

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

where \binom{m_i}{n_i} = 0 if n_i > m_i for any i.^[4]^[5]

History

Lucas's theorem was introduced by the French mathematician Édouard Lucas in 1878 as a key result in his study of simply periodic numerical functions. In his paper "Théorie des fonctions numériques simplement périodiques," published in the American Journal of Mathematics, Lucas developed the theorem in Section XXI (pp. 229–230) to provide an efficient method for determining binomial coefficients modulo a prime, expressed in terms of the base-p digits of the arguments.^[1] This approach marked a significant advancement in computational number theory during the late 19th century.^[6] Lucas's motivation stemmed from his broader investigations into periodic continued fractions and the combinatorial properties of binomial coefficients, particularly their behavior under modular arithmetic.^[1] He sought to link the periodic nature of certain numerical functions—such as those arising in trigonometric congruences—to patterns in Pascal's triangle modulo primes, simplifying calculations that were otherwise laborious.^[7] Prior to Lucas, mathematicians including Leonhard Euler had explored binomial coefficients and their expansions, laying groundwork in series and congruences, while Ernst Kummer's 1852 theorem addressed the exact power of a prime dividing a binomial coefficient through the number of carries in base-p addition.^[1] However, Lucas innovated by focusing directly on the modular value via a product over digit-wise binomial coefficients, offering a more accessible criterion for non-zero residues modulo p.^[8] Following its initial publication, Lucas's theorem saw limited immediate attention but gained renewed interest in the mid-20th century through alternative proofs and applications. In 1947, Nathan Fine provided an influential algebraic proof using generating functions, which helped popularize the result among combinatorists and number theorists.^[9] Fine's exposition in the American Mathematical Monthly emphasized the theorem's utility for counting non-zero binomial coefficients modulo a prime, bridging it to broader congruence problems.^[1] This work contributed to the theorem's enduring role in 19th- and 20th-century developments in modular arithmetic.^[10]

Proofs

Combinatorial proof

A combinatorial proof of Lucas's theorem uses a group action on the set X of all n-element subsets of an m-element set S, where the cardinality of X is \binom{m}{n}, and the fixed points under this action yield the desired product formula modulo p. Consider non-negative integers m and n expressed in base p with k+1 digits: m = m_k p^k + \cdots + m_1 p + m_0 and n = n_k p^k + \cdots + n_1 p + n_0, where $0 \leq m_i, n_i < p for each i. Let S be an m-element set partitioned into disjoint blocks S_i for i = 0, \dots, k, where |S_0| = m_0 and |S_i| = m_i p^i for i \geq 1. The set X consists of all n-element subsets of S. The elementary abelian p-group G = (\mathbb{Z}/p\mathbb{Z})^{k+1} acts on S (and thus on X) by independently cycling the p identical copies within each block S_i (for i \geq 1) according to the components of group elements, leaving S_0 fixed.^[11] The orbits of this action on X correspond to choices of "carries" when adding the base-p digits of n to themselves (or equivalently, to the ways the subset selection propagates across blocks via the cycling). Non-trivial orbits have sizes that are powers of p, hence divisible by p. The fixed points of the action—subsets unchanged by any element of G—are those that select entire cycles in each block S_i (for i \geq 1) along with exactly n_0 elements from S_0. Such fixed points are in one-to-one correspondence with choices of n_i full cycles from the m_i available in each block i, combined with a choice of n_0 elements from S_0. Thus, the number of fixed points is \prod_{i=0}^k \binom{m_i}{n_i}.^[11] Since G is a p-group of order p^{k+1}, the orbit-stabilizer theorem (or an adaptation of Burnside's lemma for p-groups) implies that |X| \equiv (number of fixed points) \pmod{p}, as all non-fixed orbits contribute multiples of p to the count. Therefore, \binom{m}{n} \equiv \prod_{i=0}^k \binom{m_i}{n_i} \pmod{p}. This holds under the assumption that p is prime, ensuring the group structure and the divisibility properties of orbit sizes.^[11]

Generating functions proof

One approach to proving Lucas's theorem employs generating functions over the polynomial ring (\mathbb{Z}/p\mathbb{Z})[X], where p is prime. This algebraic proof, originally formulated by Nathan Fine in 1947, leverages the structure of binomial expansions modulo p and the base-p representations of the integers involved.^[12] The proof begins with the fundamental identity known as the freshman's dream: for a prime p,

(1 + X)^p \equiv 1 + X^p \pmod{p}

in (\mathbb{Z}/p\mathbb{Z})[X]. This congruence follows directly from the binomial theorem, as the coefficients \binom{p}{k} for $1 \leq k \leq p-1 are divisible by p by Fermat's little theorem or direct computation.^[12] By induction on the exponent, this extends to higher powers: (1 + X)^{p^i} \equiv 1 + X^{p^i} \pmod{p} for any nonnegative integer i. The base case i=1 holds as above, and assuming it for i, raising both sides to the p-th power yields

(1 + X)^{p^{i+1}} = \left( (1 + X)^{p^i} \right)^p \equiv (1 + X^{p^i})^p \equiv 1 + (X^{p^i})^p = 1 + X^{p^{i+1}} \pmod{p},

using the freshman's dream again.^[12] Now consider a general nonnegative integer m with base-p expansion m = \sum_{i=0}^r m_i p^i, where $0 \leq m_i < p. The generating function for the binomial coefficients is (1 + X)^m = \prod_{i=0}^r (1 + X)^{m_i p^i}. Applying the identity above, this is congruent modulo p to

\prod_{i=0}^r (1 + X^{p^i})^{m_i}.

Each factor (1 + Y)^{m_i} with Y = X^{p^i} expands as \sum_{j=0}^{m_i} \binom{m_i}{j} Y^j = \sum_{j=0}^{m_i} \binom{m_i}{j} X^{j p^i}.^[12] To find the coefficient of X^n in this product, where n = \sum_{i=0}^r n_i p^i with $0 \leq n_i < p, select the term \binom{m_i}{n_i} X^{n_i p^i} from the i-th factor for each i. Since the exponents n_i p^i have disjoint supports in their base-p digits (no carry-over possible given the digit bounds), this choice contributes exactly X^n, and all other selections either under- or over-shoot the total exponent or introduce carries that mismatch. Thus, the coefficient of X^n is \prod_{i=0}^r \binom{m_i}{n_i} \pmod{p}. As this coefficient equals \binom{m}{n} in the original expansion, Lucas's theorem follows: \binom{m}{n} \equiv \prod_{i=0}^r \binom{m_i}{n_i} \pmod{p}.^[12] Fine's formulation highlights how this product arises naturally from the full multinomial expansion of the generating function, confirming the congruence without combinatorial interpretation.^[12]

Examples

Basic computations

To apply Lucas's theorem, express the integers n and m in base p, padding the shorter expansion with leading zeros to ensure equal length. Let the base-p digits be n = (n_k, \dots, n_0)_p and m = (m_k, \dots, m_0)_p. If m_i > n_i for any i, then \binom{n}{m} \equiv 0 \pmod{p}; otherwise, \binom{n}{m} \equiv \prod_{i=0}^k \binom{n_i}{m_i} \pmod{p}, where each small binomial coefficient \binom{n_i}{m_i} is computed directly since $0 \leq n_i, m_i < p.^[1] Consider p=2, n=5, and m=3. In base 2, $5 = (101)_2 so the digits are n_2=1, n_1=0, n_0=1; $3 = (11)_2 = (011)_2 (padded), so m_2=0, m_1=1, m_0=1. Here, m_1=1 > n_1=0, so the product includes \binom{0}{1} = 0. Explicitly, \binom{5}{3} \equiv \binom{1}{0} \cdot \binom{0}{1} \cdot \binom{1}{1} = 1 \cdot 0 \cdot 1 = 0 \pmod{2}, confirming that \binom{5}{3} = 10 is even.^[1] For p=3, n=10, and m=4, convert to base 3: $10 = (101)_3 (since $1 \cdot 9 + 0 \cdot 3 + 1 = 10), digits n_2=1, n_1=0, n_0=1; $4 = (11)_3 = (011)_3 (padded, since $0 \cdot 9 + 1 \cdot 3 + 1 = 4), digits m_2=0, m_1=1, m_0=1. Now, m_1=1 > n_1=0, yielding \binom{0}{1} = 0. Thus, \binom{10}{4} \equiv \binom{1}{0} \cdot \binom{0}{1} \cdot \binom{1}{1} = 1 \cdot 0 \cdot 1 = 0 \pmod{3}, as \binom{10}{4} = 210 and $210 \div 3 = 70.^[1] A common pitfall in these computations is neglecting to pad the base-p expansions with leading zeros, which can misalign digits and lead to incorrect products; always align to the length of the longer expansion.^[1]

Binary case for parity

When specialized to the prime p = 2, Lucas's theorem provides a criterion for determining the parity of a binomial coefficient \binom{n}{m}, stating that it is odd if and only if the binary expansion of m has no 1-bits in positions where the binary expansion of n has 0-bits.^[1] This follows from the general form of the theorem, where n and m are expressed in base 2 as n = \sum n_i 2^i and m = \sum m_i 2^i with n_i, m_i \in \{0,1\}, yielding

\binom{n}{m} \equiv \prod_i \binom{n_i}{m_i} \pmod{2}.

The local binomial coefficients modulo 2 are \binom{0}{0} \equiv 1, \binom{1}{0} \equiv 1, \binom{1}{1} \equiv 1, and \binom{0}{1} \equiv 0, so the product is 1 (odd) precisely when m_i \leq n_i for all i, meaning the support of the bits of m is a subset of that of n.^[1] This bit-subset condition is equivalent to the bitwise AND operation satisfying n \& m = m, where the bits of m are contained within those of n.^[1] For instance, consider \binom{13}{5}: the binary representations are $13 = 1101_2 (bits at positions 0, 2, 3) and $5 = 0101_2 (bits at positions 0, 2), so the bits of 5 form a subset of those of 13, implying \binom{13}{5} is odd; indeed, its value is 1287, which is odd. This parity criterion via binary digits simplifies computations and reveals patterns in Pascal's triangle modulo 2, such as the Sierpinski triangle structure.^[1]

Consequences

Divisibility criteria

A key corollary of Lucas's theorem provides a criterion for when a prime p divides the binomial coefficient \binom{m}{n}. Specifically, \binom{m}{n} \equiv 0 \pmod{p} if and only if, in the base-p expansions of m = \sum m_i p^i and n = \sum n_i p^i (with $0 \leq m_i, n_i < p), there exists at least one index i such that n_i > m_i.^[1] In this case, the product \prod \binom{m_i}{n_i} \pmod{p} includes a factor \binom{m_i}{n_i} = 0 since the binomial coefficient is zero when the bottom argument exceeds the top.^[1] This divisibility condition can be interpreted combinatorially in terms of base-p arithmetic: \binom{m}{n} is not divisible by p precisely when the subtraction m - n in base p requires no borrowing (i.e., m_i \geq n_i for every digit position i), ensuring that each local binomial coefficient \binom{m_i}{n_i} is nonzero modulo p.^[6] Equivalently, this corresponds to no carries occurring when adding n and m - n in base p to recover m, though the digit-wise dominance directly follows from the theorem.^[1] For example, consider p = 5, m = 7 = 1 \cdot 5 + 2 = 12_5, and n = 3 = 0 \cdot 5 + 3 = 03_5. Here, the units digit satisfies n_0 = 3 > 2 = m_0, so \binom{7}{3} \equiv 0 \pmod{5}. Indeed, \binom{7}{3} = 35, which is divisible by 5.^[6] A broader consequence is that the number of integers n (with $0 \leq n \leq m) such that \binom{m}{n} is not divisible by p equals \prod_i (m_i + 1), as for each digit position i, there are exactly m_i + 1 choices for n_i (namely, $0 to m_i) that avoid divisibility. This product formula, derived from Lucas's theorem, quantifies the sparsity of nonzero entries modulo p in the m-th row of Pascal's triangle.

Relation to Kummer's theorem

Kummer's theorem, established by Ernst Kummer in 1852, asserts that for a prime p and nonnegative integers m \geq n, the p-adic valuation v_p\left(\binom{m}{n}\right) equals the number of carries required when adding the base-p digits of n and m-n to yield the base-p expansion of m.^[13] This result connects directly to Lucas's theorem from 1878, which computes \binom{m}{n} \mod p via the product of binomial coefficients of the base-p digits. The condition in Lucas's theorem for \binom{m}{n} \not\equiv 0 \pmod{p}—namely, that each base-p digit n_i satisfies n_i \leq m_i—is precisely the scenario where no carries occur in the base-p addition of n and m-n, implying v_p\left(\binom{m}{n}\right) = 0.^[14] In this sense, Lucas's theorem captures the case of zero valuation under Kummer's framework, while Kummer's theorem generalizes to the full exponent by counting all carries. For example, with p=2, m=2, and n=1, the base-2 expansions are m = 10_2, n = 01_2, and m-n = 01_2; adding $01_2 + 01_2 produces one carry at the least significant bit, yielding v_2\left(\binom{2}{1}\right) = v_2(2) = [1](/page/1).^[14] Kummer's 1852 contribution predates Lucas's work by over two decades and lays the foundational valuation perspective from which the modulo-p criterion emerges as a special instance.

Generalizations

Prime power moduli

Lucas's theorem, originally stated for moduli that are prime numbers, has been generalized to prime power moduli p^k with k > 1. These extensions provide explicit formulas or recursive methods to compute binomial coefficients modulo p^k, building on the base-p digit decomposition but incorporating higher-order corrections.^[15] A key result for the case k=2 expresses the binomial coefficient in terms of the standard Lucas product adjusted by a linear term involving harmonic numbers. Specifically, for a prime p, nonnegative integers a, b, and $0 \leq s \leq r \leq p-1,

\binom{pa + r}{pb + s} \equiv \binom{a}{b} \binom{r}{s} \left[ 1 + p a (H_r - H_{r-s}) + p b (H_{r-s} - H_s) \right] \pmod{p^2},

where H_n = \sum_{j=1}^n \frac{1}{j} denotes the nth harmonic number, with H_0 = 0. This formula holds because the higher-order terms arise from expansions of factorials or gamma functions in the p-adic sense, capturing the deviation from the modulo-p case. Here, r and s are the base-p digits of the lower parts of the arguments, while a and b handle the higher digits recursively.^[16] Computing binomial coefficients modulo p^k for k > 1 is more complex than the prime case, often requiring techniques such as lifting the exponent lemma or p-adic expansions to account for carry-over effects in the base-p representations. Davis and Webb (1990) developed a comprehensive framework that determines \binom{m}{n} \pmod{p^k} explicitly for any prime p and arbitrary k, using a product formula over base-p digits with correction factors that grow in complexity with k.^[15] These methods highlight the challenges, as the formulas involve multiple terms and depend on the specific prime, unlike the uniform simplicity of the original theorem. For illustration, consider p=2 and k=2, so modulo 4. The formula simplifies for cases like \binom{2a + 1}{2b}, where r=1, s=0:

\binom{2a + 1}{2b} \equiv \binom{a}{b} (1 + 2b) \pmod{4},

since H_1 - H_1 = 0 and H_1 - H_0 = 1. For a=2, b=1, the left side is \binom{5}{2} = 10 \equiv 2 \pmod{4}, and the right side is \binom{2}{1} (1 + 2 \cdot 1) = 2 \cdot 3 = 6 \equiv 2 \pmod{4}, confirming the congruence. Another computation: for a=3, b=1, \binom{7}{2} = 21 \equiv 1 \pmod{4}, and \binom{3}{1} (1 + 2) = 3 \cdot 3 = 9 \equiv 1 \pmod{4}. These examples demonstrate how the adjustment term $1 + 2b refines the modulo-2 Lucas result to achieve accuracy modulo 4.

q-analogues

The q-binomial coefficient, or Gaussian binomial coefficient, is defined by

\binom{m}{n}_q = \prod_{i=1}^n \frac{1 - q^{m+1-i}}{1 - q^i}

for nonnegative integers m \geq n \geq 0, where the product is 1 if n=0. This expression counts the number of n-dimensional subspaces of an m-dimensional vector space over the finite field with q elements, weighted by q to the power of the codimension of the flag, and specializes to the ordinary binomial coefficient \binom{m}{n} in the limit as q \to 1.^[17] A q-analogue of Lucas's theorem establishes congruences for these coefficients modulo cyclotomic polynomials, adapting the base-p digit expansion of the classical case to a base-r expansion for arbitrary positive integer r. Specifically, if n = \sum_{i=0}^k n_i r^i and m = \sum_{i=0}^k m_i r^i are the base-r expansions with digits $0 \leq n_i, m_i < r, then

\binom{n}{m}_q \equiv \prod_{i=0}^k \binom{n_i}{m_i}_q \pmod{\Phi_r(q)},

where \Phi_r(q) denotes the r-th cyclotomic polynomial.^[17] This result, known as the q-Lucas theorem, holds in the polynomial ring \mathbb{Z} and extends the classical theorem, which corresponds to the case q=1 and r=p a prime. For the prime case r=p, the congruence simplifies modulo \Phi_p(q) = \frac{q^p - 1}{q-1}.^[17] In the two-digit case, where n = k a + b and m = k r + s with $0 \leq b, s < k, the theorem yields

\binom{k a + b}{k r + s}_q \equiv \binom{a}{r}_q \binom{b}{s}_q \pmod{\Phi_k(q)},

provided the digits satisfy the necessary bounds for the binomial coefficients to be defined. This form highlights the multiplicative structure analogous to the original Lucas theorem. The q-Lucas theorem appears in earlier works, with proofs attributed to developments from the 1960s onward, and has been refined in subsequent analyses.^[18]^[17] These congruences find applications in partition theory, where q-binomial coefficients generate partitions fitting inside rectangles, and in basic hypergeometric series, facilitating evaluations and identities in q-series analysis.