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.
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.
There are several ways to prove Lucas's theorem.
One consequence of Lucas's theorem is that the binomial coefficient 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, 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.
Lucas's theorem can be generalized to give an expression for the remainder when is divided by a prime power p<sup>k</sup>. 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 p<sup>k</sup> are also given by Davis and Webb (1990) and Granville (1997).
Kummer's theorem asserts that the largest integer k such that p<sup>k</sup> divides the binomial coefficient (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.
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 where and are q-binomial coefficients, is a usual binomial coefficient, and is the kth cyclotomic polynomial (in the variable q).