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

From Number

(→Related facts) |
(→Related facts) |
||

Line 9: | Line 9: | ||

* [[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]] | * [[Quadratic nonresidue that is not minus one is primitive root for safe prime]] | ||

+ | * [[Safe prime has plus or minus two as a primitive root]] | ||

==Facts used== | ==Facts used== |

## Latest revision as of 21:48, 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
- Safe prime has plus or minus two as a primitive root

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