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?

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$. 
Remark: An interesting thing here is that even though the above bound was obtained in a straightforward manner, any significant improvement needs quite a lot of machinery. And there is a large gap between what is known and what is likely to be true. 
