Exercise 5.30

Proof. Let $\chi$ be the characteristic function of $\mathit{RR}\cup \mathit{NN}$ : if $1\le n\le p-1$, $\chi (n)=1$ if $n,n+1$ are both quadratic residues, or if $n,n+1$ are both quadratic nonresidues. Then

(if $\chi (n)=1,\left(\frac{n}{p}\right)\left(\frac{n+1}{p}\right)=1$, and $\left(\frac{n}{p}\right)\left(\frac{n+1}{p}\right)=-1$ otherwise.)

Similarly, let ${\chi }^{\prime }$ be the characteristic function of the complement $\mathit{RN}\cup \mathit{NR}$ : $\chi (n)=1$ if exactly one of the integer $n,n+1$ is a residue, $0$ otherwise. Then ${\chi }^{\prime }(n)=1-\chi (n)$, so that

Since

we obtain

To evaluate this sum $S$, note that $4n(n+1)={(2n+1)}^2-1$, so

This sum can be written $S={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{\bar{n}\in {𝔽}_p^{\text{∗}}}({(2n+1)}^2-1)∕p)={\sum }_{\bar{n}\in {𝔽}_p}({(2n+1)}^2-1)∕p)$, since $(0∕p)=0$. As $f:{𝔽}_p\to {𝔽}_p,\bar{n}\mapsto (2\bar{n}+1)$ is a bijection ( $2$ is invertible in ${𝔽}_p^{\text{∗}}$),

As $p\nmid 1$, the evaluation of this last sum is given in Exercise 5.8 : $S=-1$, so

□