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:

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

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$.