# Lucas's theorem

(Redirected from Lucas' theorem)

In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient ${\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.

## Statement

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

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

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

$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 ${\tbinom {m}{n}}=0$ if m < n.

Proofs

There are several ways to prove Lucas's theorem.

Combinatorial proof —

Let M be a set with m elements, and divide it into mi cycles of length pi for the various values of i. Then each of these cycles can be rotated separately, so that a group G which is the Cartesian product of cyclic groups Cpi acts on M. It thus also acts on subsets N of size n. Since the number of elements in G is a power of p, the same is true of any of its orbits. Thus in order to compute ${\tbinom {m}{n}}$ modulo p, we only need to consider fixed points of this group action. The fixed points are those subsets N that are a union of some of the cycles. More precisely one can show by induction on k-i, that N must have exactly ni cycles of size pi. Thus the number of choices for N is exactly $\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}$ .

Proof based on generating functions —

This proof is due to Nathan Fine.

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

${\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 ${\tbinom {p}{n}}$ . In terms of ordinary generating functions, this means that

$(1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.$ Continuing by induction, we have for every nonnegative integer i that

$(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 $m=\sum _{i=0}^{k}m_{i}p^{i}$ for some nonnegative integer k and integers mi with 0 ≤ mip-1. Then

{\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 _{n_{i}=0}^{m_{i}}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{p-1}{\binom {m_{i}}{n_{i}}}X^{n_{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}} where in the final product, ni is the ith digit in the base p representation of n. This proves Lucas's theorem.

## Consequences

• A binomial coefficient ${\tbinom {m}{n}}$ is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding digit of m.
• In particular, ${\tbinom {m}{n}}$ is odd if and only if the binary digits (bits) in the binary expansion of n are a subset of the bits of m.

## Variations and generalizations

• Kummer's theorem asserts that the largest integer k such that pk divides the binomial coefficient ${\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.
• Andrew Granville has given a generalization of Lucas's theorem to the case of p being a power of prime.
• The q-Lucas theorem is a generalization for the q-binomial coefficients, first proved by J. Désarménien.