Lucas's theorem

For the theorem in complex analysis, see Gauss–Lucas theorem.

In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient ${\displaystyle {\tbinom {m}{n}}}$ by a prime number p in terms of the base p expansions of the integers m and n.

Lucas's theorem first appeared in 1878 in papers by Édouard Lucas.^[1]

Statement

For non-negative integers m and n and a prime p, the following congruence relation holds:

${\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}$

where

${\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}$

and

${\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}$

are the base p expansions of m and n respectively. This uses the convention that ${\displaystyle {\tbinom {m}{n}}=0}$ if m < n.

Proofs

There are several ways to prove Lucas's theorem.

Combinatorial proof using a group action

Let M be a set with m elements, and arbitrarily divide it into m_i cycles of length pⁱ for the various values of i. Then each of these cycles can be rotated separately by a cyclic group C_pⁱ, so that the group G which is the Cartesian product of all these cyclic groups (one for each cycle) acts on M. It thus also acts on the set of n-element subsets N of M, the number of which is ${\displaystyle {\tbinom {m}{n}}}$. This is the group action we consider in the sequel.

Since the number of elements in G is a power of p, the same is true of any of its orbits, by the orbit-stabilizer theorem. Hence, ${\displaystyle {\tbinom {m}{n}}}$ is congruent modulo p to the number of sets N whose orbit is of size 1, i.e., to the number of fixed points of the group action.

Since all cycles can be independently rotated by our group G, the fixed points of the action are those subsets N that are a union of some of the cycles. This means that N must consist of exactly n_i cycles of size pⁱ for each i, for the same reason that the integer n has a unique representation in base p. Thus the number of choices for N is exactly ${\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}}$.

Proof based on generating functions

This proof is due to Nathan Fine.^[2]

If p is a prime and n is an integer with 1 ≤ n ≤ p − 1, then the numerator of the binomial coefficient

${\displaystyle {\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}}$

is divisible by p but the denominator is not. Hence p divides ${\displaystyle {\tbinom {p}{n}}}$. Because of the binomial theorem, this means that

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

Continuing by induction, we have for every nonnegative integer i that

${\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.}$

Now let m be a nonnegative integer, and let p be a prime. Write m in base p, so that ${\displaystyle m=\sum _{i=0}^{k}m_{i}p^{i}}$ for some nonnegative integer k and integers m_i with 0 ≤ m_i ≤ p − 1. Then

${\displaystyle {\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{m_{i}}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{p-1}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}}.\end{aligned}}}$

In the last equality we use distributivity and the fact that the representation of n in base p is unique, where n_i is the i-th digit in the base p representation of n. Comparing the coefficients of Xⁿ in the very first and last sum, we obtain Lucas's theorem.

Pascal's triangle, showing the odd binomial coefficients in black.

Consequences

One consequence of Lucas's theorem is that the binomial coefficient ${\displaystyle {\tbinom {m}{n}}}$ is divisible by the prime p if and only if at least one of the digits of the base-p representation of n is greater than the corresponding digit of m. In particular, ${\displaystyle {\tbinom {m}{n}}}$ is odd if and only if the positions of the ones in the binary expansion of n are a subset of the positions of the ones in that of m. This leads to a peculiar distribution of odd numbers in Pascal's triangle, resembling Sierpiński 's triangle, shown to the right.

Non-prime moduli

Lucas's theorem can be generalized to give an expression for the remainder when ${\displaystyle {\tbinom {m}{n}}}$ is divided by a prime power p^k. However, the formulas become more complicated.

If the modulo is the square of a prime p, the following congruence relation holds for all 0 ≤ s ≤ r ≤ p − 1, a ≥ 0, and b ≥ 0:

${\displaystyle {\binom {pa+r}{pb+s}}\equiv {\binom {a}{b}}{\binom {r}{s}}(1+pa(H_{r}-H_{r-s})+pb(H_{r-s}-H_{s})){\pmod {p^{2}}},}$

where ${\displaystyle H_{n}=1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\cdots +{\tfrac {1}{n}}}$ is the nth harmonic number.^[3] Generalizations of Lucas's theorem for higher prime powers p^k are also given by Davis and Webb (1990)^[4] and Granville (1997).^[5]

Kummer's theorem asserts that the largest integer k such that p^k divides the binomial coefficient ${\displaystyle {\tbinom {m}{n}}}$ (or in other words, the valuation of the binomial coefficient with respect to the prime p) is equal to the number of carries that occur when n and m − n are added in the base p.

q-binomial coefficients

There is a generalization of Lucas's theorem for the q-binomial coefficients. It asserts that if a, b, r, s, k are integers, where 0 ≤ b, s < k, then $${\displaystyle {\begin{bmatrix}ka+b\\kr+s\end{bmatrix}}_{q}\equiv {\binom {a}{r}}{\begin{bmatrix}b\\s\end{bmatrix}}_{q}\mod {\Phi _{k}},}$$ where ⁠${\displaystyle {\begin{bmatrix}ka+b\\kr+s\end{bmatrix}}_{q}}$⁠ and ⁠${\displaystyle {\begin{bmatrix}b\\s\end{bmatrix}}_{q}}$⁠ are q-binomial coefficients, ${\displaystyle {\binom {a}{r}}}$ is a usual binomial coefficient, and ⁠${\displaystyle \Phi _{k}}$⁠ is the kth cyclotomic polynomial (in the variable q).^[6]