Quadratic nonresidue equals primitive root for Fermat prime

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 .

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 .