In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient 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: where and are the base p expansions of m and n respectively. This uses the convention that if m < n.

Proofs

There are several ways to prove Lucas's theorem.

Consequences

Non-prime moduli

Lucas's theorem can be generalized to give an expression for the remainder when \tbinom mn is divided by a prime power pk. 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. where is the nth harmonic number. Generalizations of Lucas's theorem for higher prime powers pk are also given by Davis and Webb (1990) and Granville (1997).

Variations and generalizations