Lucas's theorem

Template:Short description Template:For In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient $(\genfrac{}{}{0ex}{}{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:

$(\genfrac{}{}{0ex}{}{m}{n})\equiv \prod _{i=0}^k(\genfrac{}{}{0ex}{}{m_i}{n_i})(\mathrm{mod}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 $(\genfrac{}{}{0ex}{}{m}{n})=0$ if m < n.

Proofs

There are several ways to prove Lucas's theorem.

Consequences

• A binomial coefficient $(\genfrac{}{}{0ex}{}{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, $(\genfrac{}{}{0ex}{}{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.

Non-prime moduli

Lucas's theorem can be generalized to give an expression for the remainder when $(\genfrac{}{}{0ex}{}{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.

$(\genfrac{}{}{0ex}{}{pa+r}{pb+s})\equiv (\genfrac{}{}{0ex}{}{a}{b})(\genfrac{}{}{0ex}{}{r}{s})(1+pa(H_r-H_{r-s})+pb(H_{r-s}-H_s))(\mathrm{mod}{p}^2),$

where $H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$ is the n^th harmonic number.

Generalizations of Lucas's theorem for higher prime powers p^k are also given by Davis and Webb (1990) and Granville (1997).

Variations and generalizations

• Kummer's theorem asserts that the largest integer k such that p^k divides the binomial coefficient $(\genfrac{}{}{0ex}{}{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.

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

External links

• Template:PlanetMath
• Template:Cite journal
• Template:Cite arXiv