<s>[INST] Analogue of Fermat's "little" theorem Let $p$ be a prime, and consider $$S_p(a)=\sum_{\substack{1\le j\le a-1\\(p-1)\mid j}}\binom{a}{j}\;.$$
I have a rather complicated (15 lines) proof that $S_p(a)\equiv0\pmod{p}$. This must be
extremely classical: is there a simple direct proof ?
 [/INST] Here's a straightforward proof, using generating functions, though it's not as elegant as Ofir's.
We have
$$
\sum_{a=0}^\infty\binom{a}{j}x^a =\frac{x^j}{(1-x)^{j+1}}.
$$
Setting $j=(p-1)k$ and summing on $k$ gives
$$
\sum_{a=0}^\infty x^a \sum_{p-1\mid j}\binom{a}{j} = \frac{(1-x)^{p-1}}{(1-x)^p -x^{p-1}(1-x)}. 
$$
We subtract $\sum_{a=0}^\infty x^a \binom{a}{0} = 1/(1-x)$ and
$$\sum_{\substack{p-1\mid a\\ a>0}}x^a\binom{a}{a} = \frac{x^{p-1}}{1-x^{p-1}}$$
to get
$$
\sum_{a=0}^\infty S_p(a) x^a =  \frac{(1-x)^{p-1}}{(1-x)^p -x^{p-1}(1-x)}
 -\frac{1}{1-x} -\frac{x^{p-1}}{1-x^{p-1}}.
$$
Modulo $p$, we may replace $(1-x)^{p-1}$ with $(1-x^p)/(1-x)$ and $(1-x)^p$ with $1-x^p$, obtaining
\begin{align*}
\sum_{a=0}^\infty S_p(a) x^a &\equiv  \frac{(1-x^p)/(1-x)}{1-x^p -x^{p-1}(1-x)}
 -\frac{1}{1-x} -\frac{x^{p-1}}{1-x^{p-1}}\pmod{p}\\
 &=0.
\end{align*}
</s>