Lucas's theorem

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

In number theory, the Lucas' 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' theorem first appeared in 1878 in papers by Édouard Lucas.

Formulation

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.

Consequence

• 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.

Proof

There are several ways to prove Lucas' theorem; here is a combinatorial argument. Let M be a set with m elements, and divide it into m_i cycles of length pⁱ 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 C_pⁱ 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 n_i cycles of size pⁱ. Thus the number of choices for N is exactly

$\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}.$

Variations and generalizations

• The valuation of the binomial coefficient ${\tbinom {m}{n}}$ w.r.t. a prime p equals the number of carries that occur in addition of n and (m-n) in the base p. (Kummer's theorem)
• There exists a generalization of Lucas' theorem to the case of p being a power of prime.

External links

• Lucas's Theorem at PlanetMath.