Fermat prime implies every quadratic nonresidue is a primitive root

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.