Difference between revisions of "Quadratic nonresidue equals primitive root for Fermat prime"

From Number
Jump to: navigation, search
(Created page with '{{primitive root fact for special kind of prime}} ==Statement== Let <math>n</math> be a nonnegative integer such that the fact about::Fermat number <math>F_n</math> is prim...')
 
(Related facts)
 
(One intermediate revision by the same user not shown)
Line 8: Line 8:
  
 
* [[Prime divisor of Fermat number is congruent to one modulo large power of two]]
 
* [[Prime divisor of Fermat number is congruent to one modulo large power of two]]
 +
* [[Quadratic nonresidue that is not minus one is primitive root for safe prime]]
 
* [[Safe prime has plus or minus two as a primitive root]]
 
* [[Safe prime has plus or minus two as a primitive root]]
  

Latest revision as of 21:48, 21 April 2009

Template:Primitive root fact for special kind of prime

Statement

Let be a nonnegative integer such that the Fermat number is prime, i.e., is a Fermat prime. Then, if is a quadratic nonresidue modulo , then is a primitive root modulo .

Related facts

Facts used

  1. Euler's criterion

Proof

Given: A Fermat prime , a quadratic nonresidue modulo .

To prove: is a primitive root modulo .

Proof: We need to show that the order of modulo is .

By fact (1), if is a quadratic nonresidue modulo , . Thus, the order of modulo does not divide . On the other hand, the order divides . Thus, the order of modulo equals , so is a primitive root modulo .