Fermat prime greater than three implies three is primitive root

Statement

Suppose $n$ is a positive integer (in particular, it is not zero) such that the Fermat number $F_{n}=2^{2^{n}}+1$ is a prime number (and hence a Fermat prime). Then, the number 3 is a quadratic nonresidue modulo $F_{n}$, and hence a primitive root modulo $F_{n}$.

Related facts

• Quadratic nonresidue equals primitive root for Fermat prime
• Safe prime has plus or minus two as a primitive root

Facts used

1. Quadratic reciprocity
2. Quadratic nonresidue equals primitive root for Fermat prime

Proof

We use Fact (1), which says that, in terms of Legendre symbols:

$\left({\frac {3}{F_{n}}}\right)\left({\frac {F_{n}}{3}}\right)=(-1)^{\frac {(3-1)(F_{n}-1)}{4}}$

Note that:

• Since $n>0$, $F_{n}\equiv 1{\pmod {4}}$, so the exponent on the right side is even, so the right side is 1.
• We know that $2^{2}\equiv 1{\pmod {3}}$, so $2^{2^{n}}\equiv 1{\pmod {3}}$, so $F_{n}\equiv 2{\pmod {3}}$. Thus, $\left({\frac {F_{n}}{3}}\right)=\left({\frac {2}{3}}\right)$ which is -1.

Plugging these in, we get:

$\left({\frac {3}{F_{n}}}\right)=-1$

Thus, 3 is a quadratic nonresidue mod $F_{n}$. Combine with Fact (2) to obtain that it is a primitive root.