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{(\mathrm{mod}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$.