View source for Smallest quadratic nonresidue is less than square root plus one

==Statement==

Suppose <math>p</math> is an odd prime. Suppose <math>a</math> is the smallest positive integer less than <math>p</math> that is a [[quadratic nonresidue]] modulo <math>p</math>. Then:

<math>a < \sqrt{p} + 1</math>.

Note that we need the <math>+1</math> additive correction term. For instance, in the cases <math>p = 3</math> and <math>p = 7</math>, the smallest quadratic nonresidues (<math>2</math> and <math>3</math> respectively) are greater than the squareroot.

==Related facts==

===Other related facts and conjectures===
* [[Extended Riemann hypothesis]]: A stronger form of the Riemann hypothesis that is equivalent to the statement that the smallest quadratic nonresidue modulo <math>p</math>, for any odd prime <math>p</math>, is less than <math>3(\log p)^2/2</math>, where <math>\log</math> here is the natural logarithm.
* [[Artin's conjecture on primitive roots]]: This is a closely related conjecture that states that every integer that is not <math>-1</math> or a perfect square occurs as a primitive root for infinitely many primes.

==Proof==

'''Given''': An odd prime <math>p</math>, <math>a</math> is the smallest positive integer that is a quadratic nonresidue modulo <math>p</math>.

'''To prove''': <math>a < \sqrt{p} + 1</math>.

'''Proof''': Let <math>q</math> be the smallest positive integer such that <math>aq > p</math>, and <math>r = aq - p</math>. Since <math>p</math> is prime, <math>r \ne 0</math>, so <math>1 \le r < a</math>. Further, by the multiplicativity of Legendre symbols:

<math>\left(\frac{a}{p}\right) \left(\frac{q}{p} \right) = \left(\frac{r}{p}\right)</math>.

Since <math>a</math> is a quadratic nonresidue mod <math>p</math>, the first term is <math>-1</math>, so at least one of <math>q</math> and <math>r</math> is a nonresidue. Since <math>r < a</math> and <math>a</math> is the least nonresidue by assumption, <math>r</math> must be a quadratic residue, forcing <math>q</math> to be a quadratic nonresidue, and hence, <math>q \ge a</math>. Since <math>aq - p = r < a</math>, we get <math>q < p/a + 1</math>. In particular, since <math>a \le p/a + 1</math>, from which we can deduce that <math>a < \sqrt{p} + 1</math>.