Lucas's theorem

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

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.

Non-prime moduli

Lucas's theorem can be generalized to give an expression for the remainder when is divided by a prime power p^k. 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^k are also given by Davis and Webb and Granville.
Kummer's theorem asserts that the largest integer k such that p^k divides the binomial coefficient 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
where and are q-binomial coefficients, is a usual binomial coefficient, and is the kth cyclotomic polynomial.