Problem 2435

For rational numbers $p_{1} / q_{1}$ and $p_{2} / q_{2}$ with the denominators $q_{1}, q_{2}$ not divisible by $p$, we write $p_{1} / q_{1} \equiv p_{2} / q_{2} (\bmod p)$ if the numerator $p_{1} q_{2} - p_{2} q_{1}$ of their difference is divisible by $p$.

We start with finding an explicit formula for the residue of $S_{a}$ modulo $p$. Note first that for every $k = 1, \ldots, p-1$ the number $\binom{p}{k}$ is divisible by $p$, and
$$\frac{1}{p} \binom{p}{k} = \frac{(p-1)(p-2) \cdots (p-k+1)}{k!} \equiv \frac{(-1) \cdot (-2) \cdots (-k+1)}{k!} = \frac{(-1)^{k-1}}{k} (\bmod p)$$
Therefore, we have
$$S_{a} = -\sum_{k=1}^{p-1} \frac{(-a)^{k} (-1)^{k-1}}{k} \equiv -\sum_{k=1}^{p-1} (-a)^{k} \cdot \frac{1}{p} \binom{p}{k} \quad (\bmod p).$$
The number on the right-hand side is integer. Using the binomial formula we express it as
$$-\sum_{k=1}^{p-1} (-a)^{k} \cdot \frac{1}{p} \binom{p}{k} = -\frac{1}{p} \left(-1 - (-a)^{p} + \sum_{k=0}^{p} (-a)^{k} \binom{p}{k} \right) = \frac{(a-1)^{p} - a^{p} + 1}{p}$$
since $p$ is odd. So, we have
$$S_{a} \equiv \frac{(a-1)^{p} - a^{p} + 1}{p} (\bmod p).$$
Finally, using the obtained formula we get
$$\begin{aligned} S_{3} + S_{4} - 3 S_{2} & \equiv \frac{\left(2^{p} - 3^{p} + 1\right) + \left(3^{p} - 4^{p} + 1\right) - 3\left(1^{p} - 2^{p} + 1\right)}{p} \\ & = \frac{4 \cdot 2^{p} - 4^{p} - 4}{p} = -\frac{\left(2^{p} - 2\right)^{2}}{p} (\bmod p) \end{aligned}$$
By Fermat's theorem, $p \mid 2^{p} - 2$, so $p^{2} \mid \left(2^{p} - 2\right)^{2}$ and hence $S_{3} + S_{4} - 3 S_{2} \equiv 0 (\bmod p)$.

One may solve the problem without finding an explicit formula for $S_{a}$. It is enough to find the following property.

Lemma. For every integer $a$, we have $S_{a+1} \equiv S_{-a} (\bmod p)$.

Proof. We expand $S_{a+1}$ using the binomial formula as
$$S_{a+1} = \sum_{k=1}^{p-1} \frac{1}{k} \sum_{j=0}^{k} \binom{k}{j} a^{j} = \sum_{k=1}^{p-1} \left( \frac{1}{k} + \sum_{j=1}^{k} a^{j} \cdot \frac{1}{k} \binom{k}{j} \right ) = \sum_{k=1}^{p-1} \frac{1}{k} + \sum_{j=1}^{p-1} a^{j} \sum_{k=j}^{p-1} \frac{1}{k} \binom{k}{j} a^{k}.$$
Note that $\frac{1}{k} + \frac{1}{p-k} = \frac{p}{k(p-k)} \equiv 0 (\bmod p)$ for all $1 \leq k \leq p-1$; hence the first sum vanishes modulo $p$. For the second sum, we use the relation $\frac{1}{k} \binom{k}{j} = \frac{1}{j} \binom{k-1}{j-1}$ to obtain
$$S_{a+1} \equiv \sum_{j=1}^{p-1} \frac{a^{j}}{j} \sum_{k=1}^{p-1} \binom{k-1}{j-1} \quad (\bmod p).$$
Finally, from the relation
$$\sum_{k=1}^{p-1} \binom{k-1}{j-1} = \binom{p-1}{j} = \frac{(p-1)(p-2) \ldots (p-j)}{j!} \equiv (-1)^{j} \quad (\bmod p)$$
we obtain
$$S_{a+1} \equiv \sum_{j=1}^{p-1} \frac{a^{j} (-1)^{j}}{j!} = S_{-a}.$$
Now we turn to the problem. Using the lemma we get
$$\begin{equation*} S_{3} - 3 S_{2} \equiv S_{-2} - 3 S_{2} = \sum_{\substack{1 \leq k \leq p-1 \\ k \text{ is even}}} \frac{-2 \cdot 2^{k}}{k} + \sum_{\substack{1 \leq k \leq p-1 \\ k \text{ is odd}}} \frac{-4 \cdot 2^{k}}{k} (\bmod p) \tag{1} \end{equation*}$$
The first sum in (1) expands as
$$\sum_{\ell=1}^{(p-1)/2} \frac{-2 \cdot 2^{2\ell}}{2\ell} = -\sum_{\ell=1}^{(p-1)/2} \frac{4^{\ell}}{\ell}$$
Next, using Fermat's theorem, we expand the second sum in (1) as
$$-\sum_{\ell=1}^{(p-1)/2} \frac{2^{2\ell+1}}{2\ell-1} \equiv -\sum_{\ell=1}^{(p-1)/2} \frac{2^{p+2\ell}}{p+2\ell-1} = -\sum_{m=(p+1)/2}^{p-1} \frac{2 \cdot 4^{m}}{2m} = -\sum_{m=(p+1)/2}^{p-1} \frac{4^{m}}{m} (\bmod p)$$
(here we set $m = \ell + \frac{p-1}{2}$). Hence,
$$S_{3} - 3 S_{2} \equiv -\sum_{\ell=1}^{(p-1)/2} \frac{4^{\ell}}{\ell} - \sum_{m=(p+1)/2}^{p-1} \frac{4^{m}}{m} = -S_{4} \quad (\bmod p)$$