Difference between revisions of "Smallest quadratic nonresidue is less than square root plus one"
(→Related facts) |
|||
| Line 1: | Line 1: | ||
==Statement== | ==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: | + | Suppose <math>p</math> is an odd prime. Suppose <math>a</math> is the [[smallest quadratic nonresidue]] modulo <math>p</math>: <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>. | <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. | 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. | ||
| + | |||
| + | In fact, since the smallest quadratic nonresidue modulo <math>p</math> must be prime, we conclude that there is a prime less than <math>\sqrt{p} + 1</math> that is a quadratic nonresidue modulo <math>p</math>. | ||
==Related facts== | ==Related facts== | ||
Revision as of 18:27, 2 May 2009
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 .
