Exercise 3.1.16* (The product of the quadratic residues is congruent to $\pm 1$)

Proof. Let $p$ be an odd number. Write ${𝔽}_p$ the field $\mathbb{Z}∕\mathit{p\mathbb{Z}}$ with $p$ elements. Then ${𝔽}_p^{\text{∗}}$ is an Abelian group. Let $S$ be the subset of squares if ${𝔽}_p^{\text{∗}}$:

(Note that $r$ is a quadratic residue modulo $p$ if and only if ${[r]}_p\in S$.)

Then $S$ is a subgroup of ${𝔽}_p^{\text{∗}}$:

• $1=1^2\in S$, so $S\ne \varnothing$.
• If $y\in S,z\in S$, then $y=a^2,z=b^2$ for some $a,b\in S$, thus $\mathit{yz}=a^2{b}^2={(\mathit{ab})}^2\in S$.
• If $y\in S$, $y=a^2$, thus $y^{-1}={(a^2)}^{-1}={(a^{-1})}^2$, so $y^{-1}\in S$.

The last item shows that if $a$ is a quadratic residue, so that ${[a]}_p\in S$, and if $b$ is an inverse of $a$ modulo $p$, i.e. $\mathit{ab}\equiv 1(\mathit{mod}p)$, then ${[b]}_p={[a]}_p^{-1}\in S$, so $b$ is a quadratic residue. By Problem $11$ (second proof), the order of $S=\mathrm{im}\phi$ is $|S|=(p-1)∕2$.

Since $x^{-1}\in S$ for all $x\in S$, we may consider the map

For all $x\in S$, $(g\circ g)(x)={(x^{-1})}^{-1}=x$, so $g\circ g=1_S$, $g$ is an involution. If $x$ is a fixed point for $g$, then $x^{-1}=x$, so $x^2=1$. Since ${𝔽}_p$ is a field, $x=1$ or $x=-1$, which are their own inverses. The element $1$ is always in $S$, but $-1\in S$ if and only if $\left(\frac{-1}{p}\right)=1$, that is if $p\equiv 1(\mathit{mod}4)$.

• If $p\equiv 1(\mathit{mod}4)$, we obtain a partition of $S$ with pairs $\{x,x^{-1}\}$, where $x\ne \pm 1$, and singletons $\{-1\},\{1\}$. There are $2$ singletons, and $(p-5)∕4$ pairs:

  $$S=\{\{-1\},\{1\},\{x_1,x_1^{-1}\},\{x_2,x_2^{-1}\},\dots ,\{x_{(p-5)∕4},x_{(p-5)∕4}^{-1}\}\}.$$

  Therefore

  $$\underset{y\in S}{\prod }y=-\underset{i=1}{\overset{(p-5)∕4}{\prod }}(x_i{x}_i^{-1})=-1.$$

• If $p\equiv 3(\mathit{mod}4)$, we obtain a partition of $S$ with pairs $\{x,x^{-1}\}$, where $x\ne 1$, and singleton $\{1\}$. There are $1$ singleton, and $(p-3)∕4$ pairs:

  $$S=\{1\}\cup \{x_1,x_1^{-1}\}\cup \{x_2,x_2^{-1}\}\cup \cdots \cup \{x_{(p-3)∕4},x_{(p-3)∕4}^{-1}\}.$$

  Therefore

  $$\underset{y\in S}{\prod }y=\underset{i=1}{\overset{(p-3)∕4}{\prod }}(x_i{x}_i^{-1})=1.$$

Write $s={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{r\in R}r$ the product of quadratic residues in $[[1,p[[$, where

as in Problem 15. Then ${[s]}_p={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{y\in S}y$. Therefore