Exercise 5.29

Proof. Let $E=[[1,p-2]]$. Then $|E|=p-2$.

Write $\mathit{RR}$ the set of integers $n\in E$ such that $n$ and $n+1$ are both a quadratic residues, and $(\mathit{RR})=|\mathit{RR}|$ its cardinality, and similar definitions for $\mathit{RN},\mathit{NR},\mathit{NN}$.

As $E=\mathit{RR}\cup \mathit{RN}\cup \mathit{NR}\cup \mathit{NN}$ (disjoint union),

$\text{∙}$ The union $\mathit{RR}\cup \mathit{RN}$ is the set of $n\in E$ such that $n$ is a quadratic residue. Its cardinality is the number of quadratic residues in $[[1,p-2]]$, that is the number of quadratic residues in $[[1,p-1]]$, minus $s$, where $s=1$ if $p-1\equiv -1$ is a residue, $s=0$ otherwise. Since $\left(\frac{-1}{p}\right)={(-1)}^{(p-1)∕2}$, we obtain $s=\frac{1+{(-1)}^{\frac{p-1}{2}}}{2}$, and the total number of quadratic residues is $(p-1)∕2$, thus

$\text{∙}$ Similarly, $(\mathit{NR})+(\mathit{NN})$ is the number of quadratic nonresidues in $[[1,p-1]]$, minus $t$, where $t=1$ if $p-1$ is a quadratic nonresidue, $t=0$ otherwise : $t=\frac{1-{(-1)}^{\frac{p-1}{2}}}{2}$, so

(the sum of these two results is indeed $p-2=|E|$).

$\text{∙}$ Since $1$ is a residue, $(\mathit{RR})+(\mathit{NR})$ is the number of residues in $[[1,p-1]]$, minus $1$ :

$\text{∙}$ $(\mathit{RN})+(\mathit{NN})$ is the number of nonresidues in $[2,p-1]$, equal to the number of residues in $[[1,p-1]]$ :

□