2
$\begingroup$

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?

  • 0
    This 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 1

6

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.

  • 0
    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$.2012-05-28
  • 0
    Got turned around with non-s. You're completely correct, of course. Thanks!2012-05-28
  • 0
    Decided to use abbreviations NR, QR in hopes of greater clarity.2012-05-28
  • 0
    I believe the square root bound is due to Gauss.2012-05-31