Why is $n\choose k$ periodic modulo $p$ with period $p^e$? Given some integer $k$, define the sequence $a_n={n\choose k}$. Claim: $a_n$ is periodic modulo a prime $p$ with the period being the least power $p^e$ of $p$ such that $k<p^e$.
In other words, $a_{n+p^e}\equiv a_{n} (\text{mod } p)$. But the period $p^e$ is smaller than I'd have expected (it is obvious that a period satisfying $k! < p^e$ would work). So how can I prove that it works?
 A: It is relatively easy to show that if the base $p$ expansions of $n$ and $k$ are $n=\sum_{i\ge0} n_ip^i$ and $k=\sum_{i=0}^{e-1} k_ip^i$,
with $0\le n_i,k_i<p$ for all $i$, then
$$
{n\choose k}\equiv\prod_{i\ge0}{n_i\choose k_i} \pmod p .
$$
Here we interpret ${a\choose b}$ as equal to zero, whenever $0<a<b$. Your observation follows from the fact that adding $p^e$ to $n$ only affects the base $p$-digits $n_i, i\ge e$. Those factors are all equal to one in the above factorization, because $k_i=0$ for $i\ge e$.

Edit: Sketching a proof of Lucas' correspondence. This relies on the fact that $(a+b)^p= a^p+b^p$ in any commutative ring of characteristic $p$. Compute in the polynomial ring $F_p[x]$:
$$
\begin{aligned}
\sum_{k=0}^n{n\choose k}x^k= (1+x)^n&=(1+x)^{\sum_i n_ip^i}\\&=\prod_i\left((1+x)^{p^i}\right)^{n_i}\\
&=\prod_i(1+x^{p^i})^{n_i}\\
&=\prod_i\left(\sum_{k_i}{n_i\choose k_i}x^{k_ip^i}\right).\end{aligned}
$$
Locate the terms of degree $k$ on both sides to get the claimed congruence.
A: Here's a slightly different proof, we can use generating function in $\mathbb{F}_p[X]$,
$$(1+X)^{n+p^e} = (1+X)^n(1+X)^{p^e}$$
We can use the fact $(1+X)^p=1+X^p$ to simplify the rightmost term by repeated powers of $p$,
$$(1+X)^{n+p^e} = (1+X)^n(1+X^{p^e})$$
Now we can expand the binomial series on both sides,
$$\sum_{k=0}^{n+p^e}\binom{n+p^e}{k}X^k = \sum_{k=0}^{p^e-1} \binom{n}{k}X^k + X^{p^e}(\cdots)$$
Since we only care about the terms when $k<p^e$ we can ignore the higher terms on the right hand side and equate the coefficients which lie in $\mathbb{F}_p$,
$$\binom{n+p^e}{k} = \binom{n}{k}$$
