Let $p$ be an odd prime. Prove that: $$\sum_{k=1}^{p−1}{k^{2p−1}}\equiv\dfrac{p(p + 1)}{2}\pmod {p^2}$$

The problem is taken from the 2004 Canada National Olympiad.

I am only able to show that the sum is congruent to $0$ modulo $p$ (no congruence modulo $p^2$).

Since no value of $k$ is divisible by $p$, we have by Fermat's Little Theorem

$$k^{p-1}\equiv1\pmod p\implies k^{p-1}=np+1\text{ for an }n\in\mathbb{Z^+}$$
so then $$\begin{align} k^{2(p-1)}=1+2np+p^2&\equiv 1+p\pmod {2p} \\ &\equiv 1\pmod p \end{align}$$

But this does no better than $$k^{2p-1}\equiv k\quad(\mod p)$$ Hence, $$\begin{align} \sum_{k=1}^{p−1}{k^{2p−1}}&\equiv\dfrac{p(p - 1)}{2}\pmod p \\ &\equiv 0\pmod p \end{align}$$

which is trivial.

  • $\begingroup$ It's much easier to show the $\pmod p$ case since this congruent to $$\sum_{k=1}^{(p-1)/2} \left(k^{2p-1} +(-k)^{2p-1}\right)\equiv 0\pmod p$$ since $2p-1$ is odd. That pairing is essentially the same pairing in my full solution $\pmod {p^2}$. $\endgroup$ – Thomas Andrews Aug 11 '15 at 0:40
  • $\begingroup$ Thanks for the edit. I've been searching for that space-efficient version of "\mod" for a while now. $\endgroup$ – Marconius Aug 11 '15 at 1:25

In general: $$(a+b)^n \equiv a^n + nba^{n-1}\pmod{b^2}.$$ Letting $a=-k, b=p, n=2p-1$, you get that $$(p-k)^{2p-1} \equiv (2p-1)pk^{2p-2} - k^{2p-1}\pmod{p^2}$$

And $k^{2p-2}=(k^2)^{p-1}\equiv 1\pmod p$, we have $$(2p-1)pk^{2p-2}\equiv -pk^{2p-2}\equiv -p\pmod {p^2}.$$

So $$(p-k)^{2p-1} \equiv -p -k^{2p-1}\pmod{p^2}$$ So $$2\sum_{k=1}^{p-1} k^{2p-1} = \sum_{k=1}^{p-1} \left(k^{2p-1}+(p-k)^{2p-1}\right) \equiv -p(p-1)\equiv p\equiv p^2+p\pmod{p^2}$$

  • $\begingroup$ Thanks. That makes a lot of sense: the binomial theorem combined with the pairing Gauss used to sum $1,2,3,\ldots,100$ so quickly. $\endgroup$ – Marconius Aug 11 '15 at 1:23
  • $\begingroup$ Allegedly. (Re Gauss story, which is possibly to probably apocryphal.) $\endgroup$ – Thomas Andrews Aug 11 '15 at 1:25
  • $\begingroup$ @ThomasAndrews: I wonder if there is a neat combinatorial argument since the RHS is $\dbinom{p+1}2$ ? $\endgroup$ – Sandeep Silwal Aug 11 '15 at 4:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.