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.
[1] 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.
if m < n. There are several ways to prove Lucas's theorem.
Let M be a set with m elements, and divide it into mi cycles of length pi 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 Cpi 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.
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 ni cycles of size pi.
[2] If p is a prime and n is an integer with 1 ≤ n ≤ p − 1, then the numerator of the binomial coefficient is divisible by p but the denominator is not.
In terms of ordinary generating functions, this means that Continuing by induction, we have for every nonnegative integer i that Now let m be a nonnegative integer, and let p be a prime.
Then as the representation of n in base p is unique and in the final product, ni is the ith digit in the base p representation of n. This proves Lucas's theorem.
Lucas's theorem can be generalized to give an expression for the remainder when
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
[3] Generalizations of Lucas's theorem for higher prime powers pk are also given by Davis and Webb (1990)[4] and Granville (1997).