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?

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

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.

  • $\begingroup$ You meant "...as equal to 1"? $\endgroup$ – Gadi A Nov 15 '11 at 12:13
  • $\begingroup$ 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$. $\endgroup$ – Jyrki Lahtonen Nov 15 '11 at 13:42
  • $\begingroup$ This is known as the Lucas Correspondence $\endgroup$ – robjohn Nov 15 '11 at 14:13
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Nov 15 '11 at 14:15
  • $\begingroup$ Your proof is a lot slicker than the proof I came up with many years ago. $\endgroup$ – robjohn Nov 15 '11 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.