Why is it that $\sum_{k=1}^{p-1}{(k^2\mod{p})} = \frac{p(p-1)}{2} \forall p \in \mathbb{P} \land p \equiv 1 \mod{4}$?

Question

Currently dealing with a problem which contains a summation of squares modulo a prime, but I cannot find a reasoning online for it which isn't the sum of two squares problem due to matching terms.

The problem is finding where the following are true ($p \in \mathbb{P} \land p >2)$:

$ \sum_{k=1}^{p-1}{(k^2\mod{p})} = \sum_{k=1}^{p-1}{((k * (p - k))\mod{p})} = \sum_{k=1}^{p-1}{k} $

Here are the steps I have taken so far:

Obviously the rightmost side is trivial to determine as an arithmetic sum.

$ \sum_{k=1}^{p-1}{(k^2\mod{p})} = \sum_{k=1}^{p-1}{((k * (p - k))\mod{p})} = \frac{p(p-1)}{2} $

Since $k^2 \equiv (p-k)^2 \equiv p^2 - 2kp + k^2 \equiv k^2 \space ({}\mod{p})$ and $k(p-k) \equiv -k^2 \space ({}\mod p)$:

$ 2\sum_{k=1}^{\frac{p-1}{2}}{(k^2\mod{p})} = 2\sum_{k=1}^{\frac{p-1}{2}}{(-k^2\mod{p})} = \frac{p(p-1)}{2} $

And here is where I get stuck. I feel as though I've missed something dreadfully obvious here.

Answer 1

The constraint $p\equiv 1\pmod{4}$ ensures that if $a\in\{1,\ldots,p-1\}$ is a quadratic residue $\!\!\pmod{p}$ then $p-a$ is also a quadratic residue. Let us denote with $R$ the subset of $\{1,\ldots,p-1\}$ given by the quadratic residues $\!\!\pmod{p}$. Then $$ \sum_{k=1}^{p-1}\left(k^2\!\!\!\!\!\!\mod p\right)=2\sum_{r\in R}r=\sum_{r\in R}r+\sum_{r\in R}(p-r) = \sum_{k=1}^{p-1}k=\frac{p(p-1)}{2}. $$

Answer 2

Note that, since $ p \equiv 1 \mod 4 $, there exist $x$ such that $x^2 \equiv -1 \mod p$.

Thus, (it's not so trivial) we can partition $\{1,\ldots,p-1 \}$ in $\frac{p-1}{2}$ $2-$elements sets such that in any of this sets $\{a,b\}$ we have $a^2+b^2 \equiv 0 \mod p$.

So, since $0 < (a^2 \mod p) + (b^2 \mod p) < p^2$ we have $(a^2 \mod p) + (b^2 \mod p) = p$.

Finally, since there are $\frac{p-1}{2}$ sets, $$\sum\limits_{k=1}^{p-1} k^2 \mod p = p \cdot \frac{p-1}{2}$$