Proof of Lucas's theorem by generating functions

Proof

1. Let $p$ be a prime number and $m = \sum_{i=0}^{k} m_i p^i$, $n = \sum_{i=0}^{k} n_i p^i$ with digits $0 \le m_i, n_i < p$.
2. Let $R = (\mathbb{Z}/p\mathbb{Z})[x]$ be the polynomial ring over the integers modulo p. It is a commutative ring. In $R$, the sum of $j$ copies of $1$ is the class of $j$, which is $0$ for $j = p$ and nonzero for $0 < j < p$.
3. So $R$ has characteristic $p$. By the freshman's dream, $(1 + x)^p = 1 + x^p$ in $R$.
4. By induction on $i$, $(1 + x)^{p^i} = 1 + x^{p^i}$ in $R$. The case $i = 0$ is clear. If it holds for $i$, then $(1+x)^{p^{i+1}} = (1 + x^{p^i})^p = 1 + x^{p^{i+1}}$, by the freshman's dream applied to $1$ and $x^{p^i}$.
5. By the binomial theorem in $R$, for each natural number $N$, $(1 + x)^N = \sum_{j=0}^{N} \overline{\binom{N}{j}} x^j$. Here the bar is the class modulo $p$ of the binomial coefficient.
6. So the coefficient of $x^n$ in $(1+x)^m$ is the class of $\binom{m}{n}$. This also holds when $n > m$, since the coefficient is then $0$ and $\binom{m}{n} = 0$ by convention.
7. Since $m = \sum_i m_i p^i$, step 4 gives $(1 + x)^m = \prod_{i=0}^{k} \left((1+x)^{p^i}\right)^{m_i} = \prod_{i=0}^{k} (1 + x^{p^i})^{m_i}$.
8. By the binomial theorem, $(1 + x^{p^i})^{m_i} = \sum_{j=0}^{m_i} \overline{\binom{m_i}{j}} x^{j p^i}$.
9. Multiplying out, $(1 + x)^m$ is the sum, over all tuples $(j_0, \dots, j_k)$ with $0 \le j_i \le m_i$, of $\overline{\prod_i \binom{m_i}{j_i}} \, x^{\sum_i j_i p^i}$.
10. Base-$p$ digits are unique. If $\sum_i a_i p^i = \sum_i b_i p^i$ with digits in $\set{0, \dots, p-1}$, the division algorithm by $p$ gives $a_0 = b_0$. Subtracting, dividing by $p$ and repeating gives $a_i = b_i$ for all $i$.
11. In step 9 each $j_i \le m_i < p$. So by step 10, $\sum_i j_i p^i = n$ holds exactly when $j_i = n_i$ for every $i$.
12. If $n_i \le m_i$ for all $i$, exactly one tuple contributes to $x^n$, and the coefficient of $x^n$ is the class of $\prod_i \binom{m_i}{n_i}$.
13. If $n_i > m_i$ for some $i$, no tuple contributes, and the coefficient of $x^n$ is $0$. In this case $\binom{m_i}{n_i} = 0$, so the coefficient is again the class of $\prod_i \binom{m_i}{n_i}$.
14. Two equal polynomials have equal coefficients. Comparing steps 6, 12 and 13 gives $\binom{m}{n} \equiv \prod_{i=0}^{k} \binom{m_i}{n_i} \pmod p$, a congruence modulo p.