Smallest quadratic nonresidue is less than square root plus one

Statement

Suppose $p$ is an odd prime. Suppose $a$ is the smallest quadratic nonresidue modulo $p$: $a$ is the smallest positive integer less than $p$ that is a quadratic nonresidue modulo $p$. Then:

$a < \sqrt{p} + 1$.

Note that we need the $+1$ additive correction term. For instance, in the cases $p = 3$ and $p = 7$, the smallest quadratic nonresidues ($2$ and $3$ respectively) are greater than the square root.

In fact, since the smallest quadratic nonresidue modulo $p$ must be prime, we conclude that there is a prime less than $\sqrt{p} + 1$ that is a quadratic nonresidue modulo $p$.

Related facts

• Multiplicative group of a prime field is generated by all primes less than squareroot plus one

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 $p$, for any odd prime $p$, is less than $3(\log p)^2/2$, where $\log$ 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 $-1$ or a perfect square occurs as a primitive root for infinitely many primes.

Proof

Given: An odd prime $p$, $a$ is the smallest positive integer that is a quadratic nonresidue modulo $p$.

To prove: $a < \sqrt{p} + 1$.

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

$\left(\frac{a}{p}\right) \left(\frac{q}{p} \right) = \left(\frac{r}{p}\right)$.

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