# Lucas's theorem

Jump to navigation Jump to search

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.

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

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