Lucas's theorem

In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient [math]\displaystyle{ \tbinom{m}{n} }[/math] 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:

[math]\displaystyle{ \binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p, }[/math]

where

[math]\displaystyle{ m=m_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0, }[/math]

and

[math]\displaystyle{ n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0 }[/math]

are the base p expansions of m and n respectively. This uses the convention that [math]\displaystyle{ \tbinom{m}{n} = 0 }[/math] 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 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 [math]\displaystyle{ \tbinom{m}{n} }[/math] 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 [math]\displaystyle{ \prod_{i=0}^k\binom{m_i}{n_i}\pmod{p} }[/math].

Proof based on generating functions

This proof is due to Nathan Fine.

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

[math]\displaystyle{ \binom p n = \frac{p \cdot (p-1) \cdots (p-n+1)}{n \cdot (n-1) \cdots 1} }[/math]

is divisible by p but the denominator is not. Hence p divides [math]\displaystyle{ \tbinom{p}{n} }[/math]. In terms of ordinary generating functions, this means that

[math]\displaystyle{ (1+X)^p\equiv1+X^p\pmod{p}. }[/math]

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

[math]\displaystyle{ (1+X)^{p^i}\equiv1+X^{p^i}\pmod{p}. }[/math]

Now let m be a nonnegative integer, and let p be a prime. Write m in base p, so that [math]\displaystyle{ m=\sum_{i=0}^{k}m_ip^i }[/math] for some nonnegative integer k and integers m_i with 0 ≤ m_i ≤ p-1. Then

[math]\displaystyle{ \begin{align} \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_ip^i}\right)\\ & =\prod_{i=0}^{k}\left(\sum_{n_i=0}^{p-1}\binom{m_i}{n_i}X^{n_ip^i}\right)=\sum_{n=0}^{m}\left(\prod_{i=0}^{k}\binom{m_i}{n_i}\right)X^n \pmod{p}, \end{align} }[/math]

where in the final product, n_i is the ith digit in the base p representation of n. This proves Lucas's theorem.

Consequences

• A binomial coefficient [math]\displaystyle{ \tbinom{m}{n} }[/math] 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, [math]\displaystyle{ \tbinom{m}{n} }[/math] 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 p^k divides the binomial coefficient [math]\displaystyle{ \tbinom{m}{n} }[/math] (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.

• Generalizations of Lucas's theorem to the case of p being a prime power are given by Davis and Webb (1990) and Granville (1997).

• The q-Lucas theorem is a generalization for the q-binomial coefficients, first proved by J. Désarménien.

External links

• Lucas's Theorem at PlanetMath.org.
• A. Laugier; M. P. Saikia (2012). "A new proof of Lucas' Theorem". Notes on Number Theory and Discrete Mathematics 18 (4): 1–6. http://nntdm.net/papers/nntdm-18/NNTDM-18-4-01-06.pdf. 
• R. Meštrović (2014). "Lucas' theorem: its generalizations, extensions and applications (1878–2014)". arXiv:1409.3820 [math.NT].