# 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?

-
At first glance, it seems thinking of the numbers in base $p$ will help. Kummer's Theorem will probably help as well. –  Ragib Zaman Nov 15 '11 at 12:09

## 1 Answer

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.

-
You meant "...as equal to 1"? –  Gadi A Nov 15 '11 at 12:13
No. If for any $i$ we have $n_i<k_i$, then $n\choose k$ is divisible by $p$. Actually $n\choose k$ is divisible by $p$ if and only if that happens for some $i$. –  Jyrki Lahtonen Nov 15 '11 at 13:42
This is known as the Lucas Correspondence –  robjohn Nov 15 '11 at 14:13
Warm thanks, @robjohn !! I vaguely recalled that the name Lucas was somehow associated with this result, but couldn't find a useful link in time. –  Jyrki Lahtonen Nov 15 '11 at 14:15
Your proof is a lot slicker than the proof I came up with many years ago. –  robjohn Nov 15 '11 at 14:37