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.

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

Consequences

One consequence of Lucas's theorem is that the binomial coefficient $(\genfrac{}{}{0ex}{}{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, $(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{m}{n})$ is divided by a prime power p^k. However, the formulas become more complicated.

If the modulus 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 nth harmonic number. Generalizations of Lucas's theorem for higher prime powers p^k are also given by Davis and Webb (1990) and Granville (1997).

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.

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 $${\left[\begin{array}{c}ka+b\\ kr+s\end{array}\right]}_q\equiv (\genfrac{}{}{0ex}{}{a}{r}){\left[\begin{array}{c}b\\ s\end{array}\right]}_{q}mod{\mathrm{\Phi }}_k,$$ where Template:Tmath and Template:Tmath are q-binomial coefficients, $(\genfrac{}{}{0ex}{}{a}{r})$ is a usual binomial coefficient, and Template:Tmath is the kth cyclotomic polynomial (in the variable q).

External links

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