Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer
    
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
    
Got turned around with non-s. You're completely correct, of course. Thanks! –  Dylan Moreland May 28 '12 at 22:59
    
Decided to use abbreviations NR, QR in hopes of greater clarity. –  André Nicolas May 28 '12 at 23:43
    
I believe the square root bound is due to Gauss. –  Captain Darling May 31 '12 at 15:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.