Difference between revisions of "Smallest quadratic nonresidue is less than square root plus one"
(No difference)

Revision as of 13:11, 17 June 2010
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 squareroot.
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
 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 .