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

From Number
Jump to: navigation, search
 
(3 intermediate revisions by the same user not shown)
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 square root.
 +
 
 +
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==
 +
 +
* [[Multiplicative group of a prime field is generated by all primes less than squareroot plus one]]
  
 
===Other related facts and conjectures===
 
===Other related facts and conjectures===

Latest revision as of 13:12, 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 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 .