nt.number theory - Isolated quadratic residues in integers mod p

In addition to the character sum approach explained by Charles and Robin, which gives you a precise formula for the number of NRN patterns $mod p$ for any $p$, in the case $pequiv 3(mod 4)$ there is an elementary proof that avoids elliptic curves or Gauss sums. (Notation: N is quadratic non-residue, R is quadratic residue.)

I claim that it is sufficient to find an arithmetic progression $mod p$ of the form $-a^2,1,-b^2$ with non-zero $a,b.$ Indeed, $-a^2$ and $-b^2$ are N and 1 is R. Choose the sign so that $n=pm(1+a^2)$ is R: this is possible since $-1$ is a quadratic non-residue $(mod p),$ by the assumption on $p$. Dividing by $n$, we'll get three consecutive non-zero numbers $mod p$ in pattern NRN. Thus it remains to show that $a^2+b^2=-2 (mod p)$ has a solution with $a,bne 0,$ which is a special case of the well known fact that for $pgeq 7,$ any non-zero element of $mathbb{Z}/pmathbb{Z}$ is the sum of two non-zero squares. Conversely, all NRN patterns are obtained in this way and with a tiny bit of extra work, one can count that there are $(p+1)/8$ or $(p-3)/8$ of them, depending on whether $pequiv 7(mod 8)$ or $pequiv 3(mod 8).$