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?



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


