Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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