Difference between revisions of "Quadratic nonresidue equals primitive root for Fermat prime"
From Number
(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) |
||
| 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]] |
==Facts used== | ==Facts used== | ||
Revision as of 14:43, 21 April 2009
Template:Primitive root fact for special kind of prime
Contents
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
- 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
Facts used
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 .
