Quadratic nonresidue equals primitive root for Fermat prime

Statement

Let $n$ be a nonnegative integer such that the Fermat number $F_{n}$ is prime, i.e., is a Fermat prime. Then, if $a$ is a quadratic nonresidue modulo $F_{n}$, then $a$ is a primitive root modulo $F_{n}$.

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

1. Euler's criterion

Proof

Given: A Fermat prime $F_{n}$, a quadratic nonresidue $a$ modulo $F_{n}$.

To prove: $a$ is a primitive root modulo $F_{n}$.

Proof: We need to show that the order of $a$ modulo $F_{n}$ is $F_{n}-1=2^{2^{n}}$.

By fact (1), if $a$ is a quadratic nonresidue modulo $F_{n}$, $a^{(F_{n}-1)/2}\equiv -1{\pmod {F}}_{n}$. Thus, the order of $a$ modulo $F_{n}$ does not divide $(F_{n}-1)/2=2^{2^{n}-1}$. On the other hand, the order divides $F_{n}-1$. Thus, the order of $a$ modulo $F_{n}$ equals $F_{n}-1$, so $a$ is a primitive root modulo $F_{n}$.