Exercise 3.1.15 (Sum of the quadratic residues in $[1,p)$)

Proof. Let $p=4k+1$ a prime number. By Problem 15, there are $(p-1)∕2$ quadratic residues $r\in [[1,p-1]]$. Let $R$ be the set of such residues:

Then $|R|=(p-1)∕2$.

Here $p\equiv 1(\mathit{mod}4)$, thus $\left(\frac{-1}{p}\right)={(-1)}^{(p-1)∕2}=1$, so $-1$ is a quadratic residue. Since the product of quadratic residues is a quadratic residue, if $r$ is a quadratic residue modulo $p$, so is $-r$, thus the congruent number $p-r$ is also a quadratic residue. Moreover, if $1\le r\le p-1$, then $1\le p-r\le p-1$. This shows that

This allows us to define the map

For all $r\in R$, $(f\circ f)(r)=p-(p-r)=r$, so $f\circ f=1_R$. Moreover, if $f(r)=r$, then $2r=p$, where $p$ is odd, thus $p\mid r$. Since $1\le r\le p-1$, this is impossible, therefore $f(x)\ne x$ for every $r\in R$. This shows that $f$ is an involution without fixed point. Therefore we can group all residues in $R$ by pairs, so that the set of pairs $\{r,f(r)\}=\{r,p-r\}$ is a partition of $R$. Since $|R|=(p-1)∕2$, there are $(p-1)∕4$ such pairs:

where $r_1,\dots ,r_{(p-1)∕4}$ are chosen arbitrarily in each pair.

Therefore, the sum $s$ of the quadratic residues modulo $p$ in the interval $[[1,p[[$ is given by

□