Binomial congruence modulo prime number 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?
 A: 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.
A: 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.
