= Solution
Write both nonnegative <integers> $n,k$ in <base-p expansions>, padding with zero digits to a common length $L$. By the preceding polynomial identity,
$$
(1+x)^n=\prod_{i=0}^L\left((1+x)^{p^i}\right)^{n_i}\equiv\prod_{i=0}^L(1+x^{p^i})^{n_i}\pmod p.
$$
Expanding the last product with the <binomial theorem>, each term is obtained by choosing an <integer> $j_i$ with $0\le j_i\le n_i<p$. Its exponent is $\sum_i j_ip^i$ and its coefficient is $\prod_i\binom{n_i}{j_i}$. Uniqueness of <base-p expansions> says that the only way this exponent can equal $k$ is to choose $j_i=k_i$ for every $i$.
If some $k_i>n_i$, no such term exists and the coefficient is zero. Otherwise its coefficient is precisely the product below. Comparing the coefficient of $x^k$ proves <Lucas theorem>:
$$
\boxed{\binom nk\equiv\prod_{i=0}^L\binom{n_i}{k_i}\pmod p,}
$$
with the convention $\binom ab=0$ for $b>a$. This also covers $k>n$, and padding either expansion by further zero digits multiplies the product only by $\binom00=1$.
Back to article page
