Analogue of Fermat's "little" theorem

Question

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 ?

Answer 1

Let $$P(x)=(1+x)^a-1-x^a=\sum_{1 \le j \le a-1} \binom{a}{j}x^j.$$ Working in a field $F$ where $|\{\mu \in F: \mu^{p-1}=1\}|=p-1$ (roots of unity of order $p-1$ exist), we have $$ \frac{1}{p-1}\sum_{\mu^{p-1}=1}P(x \mu) = \sum_{\substack{1 \le j \le a-1\\(p-1)\mid j}} \binom{a}{j}x^j.$$ We now specialize the field to $\mathbb{F}_p$, and let $x=1$: $$ -\sum_{\mu \in \mathbb{F}_p^{\times}}P( \mu) = \sum_{\substack{1 \le j \le a-1\\(p-1)\mid j}} \binom{a}{j}.$$ To conclude, observe that $P(0)=0$ and $|\mathbb{F}_p| = p$, so $$\sum_{\mu \in \mathbb{F}_p^{\times}} P(\mu) = \sum_{\mu \in \mathbb{F}_p} P(\mu) = \sum_{\mu \in \mathbb{F}_p} ((1+\mu)^a - \mu^a)=0,$$ because $\mu\mapsto \mu+1$ is a permutation of $\mathbb{F}_p$.

---

A slightly more general congruence is due to Glaisher (1899), as I've found in a survey by Granville, see equation (11) here. The precise reference is Glaisher, J. W. L., "A congruence theorem relating to sums of binomial-theorem coefficients.", Quart. J. 30, 150-156, 349-360, 361-383 (1899). See here for the zbMath review in German. There is no entry in MathSciNet.

Namely, Glaisher proved that for any $0 \le j_0 \le p-1$ we have $$\sum_{\substack{1 \le j \le a \\ j \equiv j_0 \bmod (p-1)}} \binom{a}{j} \equiv \binom{k}{j_0} \bmod p$$ where $k$ is any positive integer with $k \equiv a \bmod p$. Applying this with $j_0=0$ and $k=a$, and observing that the term $j=a$ contributes $1 \bmod p$, your result follows. Clicking on equation (11) in the first link above leads to a detailed proof which utilizes Lucas' theorem.

Answer 2

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*}

Answer 3

Actually, a further extension was given in my paper Combinatorial congruences and Stirling numbers [Acta Arith. 126 (2007), 387-398]. Now I state Corollary 1.3 (a consequence of Theorem 1.1) in the 2007 paper of mine.

Let $p$ be a prime. If $l,l',m$ are positive integers with $l'\ge l>m/p$ and $l'\equiv l\pmod {(p-1)p^{\lfloor\log_p m\rfloor}}$, then $$\sum_{j\equiv r\pmod {p-1}}\binom{l'}j S(j,m) \equiv\sum_{j\equiv r\pmod {p-1}}\binom{l}j S(j,m)\pmod p,$$ where $S(j,m)$ denotes the Stirling number of the second kind.

In the case $m=1$, this yields Glaisher's result.