There are several ways to prove Lucas's theorem. {{Math proof|title=Combinatorial proof using a group action|drop=hidden|proof= Let
M be a set with
m elements, and arbitrarily divide it into
mi cycles of length
pi for the various values of
i. Then each of these cycles can be rotated separately by a
cyclic group Cpi, 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 \tbinom{m}{n}. This is the group action we consider in the sequel. Since the number of elements in
G is a power of
p, the same is true of any of its
orbits, by the
orbit-stabilizer theorem. Hence, \tbinom{m}{n} is congruent modulo
p to the number of sets
N whose orbit is of size 1, i.e., to the number of
fixed points of the group action. Since all cycles can be independently rotated by our group
G, the fixed points of the action are those subsets
N that are a union of some of the cycles. This means that
N must consist of exactly
ni cycles of size
pi for each
i, for the same reason that the integer
n has a unique representation in base
p. Thus the number of choices for
N is exactly \prod_{i=0}^k\binom{m_i}{n_i}. }} {{Math proof|title=Proof based on generating functions|drop=hidden|proof= This proof is due to Nathan Fine. If
p is a prime and
n is an integer with 1 ≤
n ≤
p − 1, then the numerator of the binomial coefficient : \binom p n = \frac{p \cdot (p-1) \cdots (p-n+1)}{n \cdot (n-1) \cdots 1} is divisible by
p but the denominator is not. Hence
p divides \tbinom{p}{n}. Because of the
binomial theorem, this means that :(1+X)^p\equiv1+X^p\pmod{p}. Continuing by
induction, we have for every nonnegative integer
i that :(1+X)^{p^i}\equiv1+X^{p^i}\pmod{p}. Now let
m be a nonnegative integer, and let
p be a prime. Write
m in base
p, so that m=\sum_{i=0}^{k}m_ip^i for some nonnegative integer
k and integers
mi with 0 ≤
mi ≤
p − 1. Then :\begin{align} \sum_{n=0}^{m}\binom{m}{n}X^n & =(1+X)^m=\prod_{i=0}^{k}\left((1+X)^{p^i}\right)^{m_i}\\ & \equiv \prod_{i=0}^{k}\left(1+X^{p^i}\right)^{m_i}\\ &=\prod_{i=0}^{k}\left(\sum_{j_i=0}^{m_i}\binom{m_i}{j_i}X^{j_ip^i}\right)\\ & =\sum_{n=0}^{m}\left(\prod_{i=0}^{k}\binom{m_i}{n_i}\right)X^n \pmod{p}. \end{align} In the last equality we use
distributivity and the fact that the representation of
n in base
p is unique, where
ni is the
i-th digit in the base
p representation of
n. Comparing the coefficients of
Xn in the very first and last sum, we obtain Lucas's theorem. }} == Consequences ==