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?
bound of quadratic nonresidue modulo an odd prime
-
0This http://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. – 2012-05-28
1 Answers
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.
-
0I belie$v$e the square root bound is due to Gauss. – 2012-05-31