# Smallest quadratic nonresidue is less than square root plus one

## Statement

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

.

Note that we need the  additive correction term. For instance, in the cases  and , the smallest quadratic nonresidues ( and  respectively) are greater than the square root.

In fact, since the smallest quadratic nonresidue modulo  must be prime, we conclude that there is a prime less than  that is a quadratic nonresidue modulo .

## 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 , for any odd prime , is less than , where  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  or a perfect square occurs as a primitive root for infinitely many primes.

## Proof

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

To prove: .

Proof: Let  be the smallest positive integer such that , and . Since  is prime, , so . Further, by the multiplicativity of Legendre symbols:

.

Since  is a quadratic nonresidue mod , the first term is , so at least one of  and  is a nonresidue. Since  and  is the least nonresidue by assumption,  must be a quadratic residue, forcing  to be a quadratic nonresidue, and hence, . Since , we get . In particular, since , from which we can deduce that .