Binomial congruence modulo prime number

Question

Let $1\leq{j}<p-1$ with $p$ a prime number. Is it true that for any positive integer $n$ with $n\not\equiv{j} \pmod{p-1}$ the congruence $$\sum_{r>1}{n\choose r(p-1)+j}{r-1\choose j}\equiv 0 \pmod p$$ is valid?

Answer 1

Yes, this congruence is, in fact, true. To see this, notice first that $$ {r(p-1)+j\choose j}=\frac{(r(p-1)+j)\ldots (r(p-1)+1)}{j!}\equiv $$ $$ \equiv \frac{(j-r)(j-1-r)\ldots(1-r)}{j!}=(-1)^j{r-1\choose j}\pmod p $$ so it's enough to show that $$ \sum_{r>1}{n\choose r(p-1)+j}{r(p-1)+j \choose j}\equiv 0 \pmod p. $$ Since for $r=1$ we get a summand equal to $0$ and for $r=0$ we get ${n \choose j}$, we see that it's enough to show that $$ \sum_{\substack{k>0\\ k\equiv j\pmod {p-1}}}{n \choose k}{k \choose j}\equiv {n\choose j} \pmod p. $$ Next, consider the polynomial $$ f_{nj}(x)=\sum_{\substack{k>0\\ k\equiv j \pmod {p-1}}}{n \choose k}x^k. $$ Since $$ \frac{d^j}{dx^j}x^k=k(k-1)\ldots(k-1+j)x^{k-j}=j!{k \choose j}x^{k-j}, $$ it is enough to show that the $j$-th derivative of $f_{nj}(x)$ is $\equiv j!{n \choose j} \pmod p$ at $x=1$.

Now, let us find an expression for our polynomial. Let $\zeta=\exp\left(\frac{2\pi i}{p-1}\right)$, then $$ \sum_{a=0}^{p-2}\zeta^{ak}=\begin{cases}0\text{ if }k\not\equiv 0\pmod{p-1},\\ p-1 \text{ if }k\equiv 0\pmod{p-1}. \end{cases} $$ This easily implies that $$ f_{nj}(x)=\frac{1}{p-1}\sum_{a=0}^{p-2}((1+\zeta^a x)^n-1)\zeta^{-aj}, $$ because $$ \sum_{k>0}{n \choose k}x^k=(1+x)^n-1. $$ Now we need to compute the $j$-th derivative. To do so, notice that $j>0$, so we can entirely ignore the constant terms. Also, $$ (1+\zeta^a x)^n\zeta^{-aj}=(\zeta^{-a}+x)^n\zeta^{(n-j)a}, $$ hence $$ \frac{d^j}{dx^j}f_{nj}(x)=\frac{1}{p-1}\sum_{a=0}^{p-2}n(n-1)\ldots(n-j+1)(\zeta^{-a}+x)^{n-j}\zeta^{-a(n-j)}= $$ $$ =j!{n \choose j}\frac{1}{p-1}\sum_{a=0}^{p-2}(1+\zeta^a x)^{n-j}. $$ So, for our purposes it suffices to show that $$ \frac{1}{p-1}\sum_{a=0}^{p-2}(1+\zeta^a)^M \equiv 1 \pmod p $$ for $M\not \equiv 0 \pmod{p-1}$ (we take $M=n-j$). To prove that, notice that for any algebraic integer $\alpha$ we have $(1+\alpha)^p\equiv 1+\alpha^p \pmod p$. Also, $\zeta^p=\zeta$. Therefore, if $M=M_np^n+\ldots+M_0$, then for $0\leq i\leq n$ $$ (1+\zeta^a)^{M_ip^i}=((1+\zeta^a)^{p^i})^{M_i}\equiv (1+\zeta^{ap^i})^{M_i}=(1+\zeta^a)^{M_i} \pmod p, $$ consequently, $$ (1+\zeta^a)^M \equiv (1+\zeta^a)^{M_n+\ldots+M_0} \pmod p. $$ This means that we can replace $M$ by the sum of its $p$-ary digits. Iterating this procedure until we get a single-digit number $m$, we see that $0<m<p$ and also $$ M\equiv m\pmod{p-1}, $$ because $p^i\equiv 1 \pmod{p-1}$. This means that actually $1\leq m\leq p-2$. Finally, $$ \frac{1}{p-1}\sum_{a=0}^{p-2}(1+\zeta^a)^m=\frac{1}{p-1}\sum_{a=0}^{p-2}\sum_{l=0}^m{m\choose l}\zeta^{al}={m \choose 0}=1 $$ (see identity for sums of $\zeta^{al}$ above) This concludes the proof.

Answer 2

Here is short proof based on Bachmann's result from 1867: (L.E.Dickson,History of the theory of Numbers,Vol.I,Chapter XI)

B. $\sum_{r\geq 1}{n\choose r(p-1)}\equiv 0(\mod p)$

Let us begin with the well known property of the binnomial coeficients $k\cdot{n \choose k}=n\cdot{n-1\choose k-1}$
If we iterate this equation $j$-times and put $k=r\cdot(p-1)+j$,

we get

$(r(p-1)+j)(r(p-1)+j-1)...(r(p-1)+1)\cdot{n\choose (r(p-1)+j)}=n(n-1)..(n-j+1)\cdot{n-j\choose r(p-1)}$

Left hand side of eq. is $\equiv(-1)^j{j!}{r-1\choose j}(\mod{p})$
and by suming both sides modulo $p$ over $r$

$(-1)^j{j!}\sum_{r}{n\choose (r(p-1)+j)}{r-1\choose j}\equiv{n(n-1)..(n-j+1)\sum_r{n-j\choose r(p-1)}}$

After B. the right hand side is $\equiv0(\mod p-1)$ and so is left hand side, and since $j! \not\equiv{0}(\mod p)$ , this conclude the proof.