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?

Solution 1:

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.