# bound of quadratic nonresidue modulo an odd prime

I heard that if $p$ is an odd prime, there is a quadratic nonresidue modulo $p$ less than $p^{1/2} +1$. How to show this statement?

-
This oeis.org/A000229 is, roughly speaking, a list of primes with astonishingly large first quadratic nonresidues. And the first nonresidues are still tiny. So, computational experience says pretty strongly that one can do better than $\sqrt p,$ but proofs are hard to come by. – Will Jagy May 28 '12 at 23:01

Let $s$ be the smallest positive quadratic non-residue (NR) of $p$. Divide $p$ by $s$. We get $p=qs+r$ where $1 \le r \lt s$. It follows that $p=(q+1)s -(s-r)$, and therefore $$s(q+1)\equiv s-r \pmod{p}.\tag{1}$$ Since $s-r \lt s$, the number $s-r$ is a quadratic residue (QR) of $p$, and therefore by $(1)$, $s(q+1)$ is a QR. Recall that the product of an NR and a QR is an NR. So if $q+1$ were a QR, then $s(q+1)$ would be an NR, which is not the case. It follows that $q+1$ must be an NR, and therefore $q+1 \ge s$.
Thus $q \ge s-1$. But $qs \lt p$, so $s(s-1) \le p-1$. From this, by completing the square, we can conclude that $$s \le \sqrt{p-\frac{3}{4}} +\frac{1}{2}$$
We have equality at least at $p=3$ and $p=7$.
I mean to say that $q+1$ is a non-residue. For (as mentioned) $s$ is a non-residue. If $q+1$ were a residue, then since $s(q+1)\equiv s-r\pmod{p}$, $s-r$ would be a non-residue, but it is a residue, by the minimality of $s$. – André Nicolas May 28 '12 at 22:54