Fermat prime implies every quadratic nonresidue is a primitive root
From Number
Contents
Statement
Suppose is a Fermat prime. Then, every quadratic nonresidue modulo
is a primitive root modulo
. The number of these elements is
.
Related facts
- Primitive root implies quadratic nonresidue for modulus greater than two
- Safe prime has plus or minus two as a primitive root
- Quadratic nonresidue that is not minus one is primitive root for safe prime
Proof
Proof idea
Let .
The idea is that if an element is not a primitive root, then we must have
, which, by Euler's criterion for quadratic residues, implies that
is a quadratic residue. Thus, every quadratic nonresidue is a primitive root. The same argument establishes the converse.