# Difference between revisions of "Smallest quadratic nonresidue is less than square root plus one"

(Created page with '==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 ...') |
|||

Line 9: | Line 9: | ||

==Related facts== | ==Related facts== | ||

+ | ===Stronger facts=== | ||

+ | |||

+ | * [[Subgroup of multiplicative group of prime field is generated by elements 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 <math>p</math>, for any odd prime <math>p</math>, is less than <math>3(\log p)^2/2</math>, where <math>\log</math> here is the natural logarithm. | * [[Extended Riemann hypothesis]]: A stronger form of the Riemann hypothesis that is equivalent to the statement that the smallest quadratic nonresidue modulo <math>p</math>, for any odd prime <math>p</math>, is less than <math>3(\log p)^2/2</math>, where <math>\log</math> 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 <math>-1</math> or a perfect square occurs as a primitive root for infinitely many primes. | * [[Artin's conjecture on primitive roots]]: This is a closely related conjecture that states that every integer that is not <math>-1</math> or a perfect square occurs as a primitive root for infinitely many primes. |

## Revision as of 13:19, 21 April 2009

## Contents

## Statement

Suppose is an odd prime. Suppose 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.

## Related facts

### Stronger 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 .