Quadratic nonresidue equals primitive root for Fermat prime
- 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
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 .