In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient ${\displaystyle {\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.

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 ${\displaystyle {\tbinom {m}{n}}=0}$ if m < n.

There are several ways to prove Lucas's theorem.

Let M be a set with m elements, and arbitrarily divide it into m_i cycles of length pⁱ for the various values of i. Then each of these cycles can be rotated separately by a cyclic group C_pⁱ, so that the group G which is the Cartesian product of all these cyclic groups (one for each cycle) acts on M. It thus also acts on the set of n-element subsets N of M, the number of which is ${\displaystyle {\tbinom {m}{n}}}$. This is the group action we consider in the sequel.