5
$\begingroup$

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?

  • 0
    At 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 1

2

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


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.

  • 0
    You meant "...as equal to 1"?2011-11-15
  • 0
    No. If for any $i$ we have $n_i$n\choose k$ is divisible by $p$. Actually $n\choose k$ is divisible by $p$ if and only if that happens for some $i$. – 2011-11-15
  • 0
    This is known as the [Lucas Correspondence](http://mathworld.wolfram.com/LucasCorrespondenceTheorem.html)2011-11-15
  • 0
    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.2011-11-15
  • 0
    Your proof is a lot slicker than [the proof I came up with](http://www.whim.org/nebula/math/lucascorrespondence.html) many years ago.2011-11-15