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 . 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?
Why is $n\choose k$ periodic modulo $p$ with period $p^e$?
-
0At first glance, it seems thinking of the numbers in base $p$ will help. [Kummer's Theorem](http://planetmath.org/encyclopedia/KummersTheorem.html) will probably help as well. – 2011-11-15
1 Answers
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 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. 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.
-
0Your proof is $a$ lot slicker than [the proof I came up with](http://www.whim.org/ne$b$ula/math/lucascorrespondence.html) many years ago. – 2011-11-15