For prime *p* sufficiently large, there is always an integer *q* such that *q* is a residue mod *p*, but neither *q*−1 nor *q*+1 are; the number of such residues scales like *p*/8 (and similarly for any sequence of residues/non-residues in three consecutive integers). 


What are the best lower bounds on primes *p*, for which such "isolated" residues are guaranteed to exist? Do they exist, for instance, for all *p* ≡ 3 (mod 4) aside from *p* = 3?


(If this is a typical homework problem, please point me to a textbook for which it is an exercise.)



Isolated quadratic residues in integers mod p
I'll write $\chi(x)$ for the Legendre symbol modulo $p$.
Consider 
$$f(x)=(\chi(x)+1)(\chi(x-1)-1)(\chi(x+1)-1).$$
Then $f(x)=8$ if $x$ is an isolated quadratic residue and $0$ otherwise
(unless $x$ is $0$, $\pm1$ which are exceptional cases that have to be factored
in to the bookkeeping eventually). Thus $S=\sum\_{x=1}^p f(x)$
is eight times the number of isolated primes plus a fudge factor. But expanding out
$S$ gives sums such as $\sum\chi(x)$ and $\sum\chi(x(x-1))$ which are easy to deal
with, and also $T=\sum\chi(x^3-x)$. This final sum is related to the number of
points on the elliptic curve $y^2=x^3-x$ and so is bounded by $2\sqrt p$ by Hasse's
bound. But if $p\equiv3$ (mod $4$), $T=0$ as the $x$ and $-x$ terms cancel. In this
case one gets an exact formula for the number of isolated quadratic residues.


One can extend this ideal to bigger patterns of residues and nonresidues.
As the polynomials become larger
they are related to hyperelliptic curves, but from the Riemann hypothesis
for curve one can still get bounds.


