Why is this proof of a congruence relation valid?

Question

The following question comes from the 2012 Singapore Mathematical Olympiad (Open Section), Round 2.

Let $p$ be an odd prime. Show that $$1^{p-2}+2^{p-2}+3^{p-2}+\dots+\left(\frac{p-1}2\right)^{p-2}=\frac{2-2^p}{p}\pmod p.$$

After trying and failing to find a proof, I went to look at the official solution, which is as follows.

Note that for every $k=1,2,\dots,(p-1)/2$, it is true that $$\frac{2k}p\binom{p}{2k}=\frac{(p-1)(p-2)\dotsm(p-2k+1)}{(2k-1)!}=-1\pmod{p}.$$ Therefore, the LHS is $$\sum_{k=1}^{(p-1)/2}k^{p-2}=-\sum_{k=1}^{(p-1)/2}k^{p-2}\frac{2k}{p}\binom{p}{2k}=-\frac2p\sum_{k=1}^{(p-1)/2}k^{p-1}\binom{p}{2k}=-\frac2p\sum_{k=1}^{(p-1)/2}\binom{p}{2k}.$$ The summation in the last equality counts the number of even-sized nonempty subsets of a $p$-element set, which is $2^{p-1}-1$.

I have a problem with the proof, in the last equality. I know that the proof goes on the idea that $k^{p-1}=1$ for every $k\neq 0$ (Fermat's Little Theorem), but doesn't that mean that we have to work inside $\mathbb Z/p\mathbb Z$, which would make the $-\frac2p$ a division by $0$? To illustrate, suppose we claimed that $$\frac{2-2^p}p=\frac2p(1-2^{p-1})=\frac2p(1-1)=0\pmod p.\tag{1}$$ This is of course absurd, because we really have a $0/0$ in the last step, so we are dividing by $0$. Indeed we can see (for example) that $(2-2^3)/3=-2$, which is not divisible by $3$. So when we are working inside $\mathbb Z/p\mathbb Z$, it is not possible to divide by $p=0$. How, then, is the reasoning in $(1)$ fallacious, but that in the proof correct? What am I missing here?

Answer 1

The ideas behind the proof are fine, but it has been written (IMHO) somewhat carelessly. You can repair it by replacing every congruence $a\equiv b\pmod p$ by an equation $a=b+mp$ and following essentially the same argument. They also have failed to mention the important fact that $\binom{p}{2k}$ is a multiple of $p$ provided $p\not\mid k$.

In the following, to save writing, $m$ represents an integer which need not be the same every time (so for example I can write $2(m+5)=m$). We have $$\frac{2k}{p}\binom{p}{2k}=-1+mp$$ and so $$\def\sk{\sum_{k=1}^{(p-1)/2}} \eqalign{ \sk k^{p-2}&=\sk k^{p-2}\Bigl(mp-\frac{2k}{p}\binom{p}{2k}\Bigr)\cr &=mp-\frac2p\sk k^{p-1}\binom{p}{2k}\cr &=mp-\frac2p\sk (1+mp)\binom{p}{2k}\cr &=mp-\frac2p\sk \binom{p}{2k}-2m\sk\binom{p}{2k}\cr &=mp-\frac2p(2^{p-1}-1)-2m\sk mp\cr &=\frac{2-2^p}{p}+mp\ .\cr}$$ Hence, $$\sk k^{p-2}\equiv \frac{2-2^p}{p}\pmod p\ .$$

Comment. The convention "$m$ represents an integer which need not be the same every time" is exactly the reason why congruence notation is very useful. On the other hand, as your question shows, sometimes congruence notation has drawbacks too.

Answer 2

$c_k := \large -\frac{2}p\binom{p}{2k}\in\Bbb Z\,$ by $\,\large p\mid\binom{p}{2k}.\,$ $\,\color{#c00}{kc_k\equiv 1}\pmod {\!p}\,$ as they sketch. So with $\large \,\sum = \sum _{k\,=\,1}^{(p-1)/2}$

$$\bmod p\!:\,\ \sum k^{\large p-2}\equiv\sum k^{\large p-2} \color{#c00}{k\, c_k} \equiv \sum c_k =\, -\frac{2}p\sum\binom{p}{2k} =\, \frac{-2(2^{\large p-1}-1)}p\qquad\qquad$$

Note that the final $2$ equations are not congruences - they are integer equalities (the fraction $\in\Bbb Z),\,$ and the first $2$ congruences relate integers. So the proof is correct (though notation obscures that).