Exercise 3.1.21* (When is every quadratic nonresidue a primitive root?)

Proof. Let $p$ be an odd prime, and $g$ a primitive root modulo $p$. Assume for contradiction that $g$ is a quadratic residue, then $g\equiv a^2(\mathit{mod}p)$. But then $g^{(p-1)∕2}\equiv a^{p-1}\equiv 1$, thus the order of $g$ divides $(p-1)∕2$. But the order of $g$ is $p-1$ by definition. This contradiction shows that $g$ is not a quadratic residue.

(Alternatively, from Problem 11, we know that the quadratic nonresidues are $g,g^3,g^5,\dots$.)

Consider a Fermat number $p=2^{2^n}+1$, where $n\in \mathbb{N}=\{0,1,2,3,\dots \}$, and let $a$ be a quadratic residue modulo $p$. If $g$ is a chosen primitive root, then by Problem 11, $a\equiv g^t$ for some odd positive integer $t$. Let $o(x)$ denote the order of an element $x$ modulo $p$, if $p\nmid x$. Then $o(g)=p-1=2^{2^n}$. By Lemma 2.33,

and since $t$ is odd, $t\wedge 2^{2^n}=1$, thus

so $a$ is a primitive root modulo $p$. This shows that every quadratic nonresidue modulo $F_n$ is a primitive root.

Conversely, let $p$ be any odd prime, and suppose that every quadratic nonresidue is a primitive root. Let $p-1=2^a{p}_1^{a_1}{p}_2^{a_2}\cdots p_l^{a_l}$ be the factorization of $p-1$ into prime factors, where $2<p_1<p_2<\cdots <p_k$, and $a_i\ge 0$.

Let $g$ be a fixed primitive root modulo $p$. By problem 11, the quadratic non residues are the numbers $g^t$ where $t$ is odd. By our hypothesis, $g^t$ is also a primitive root, for every odd $t$. This shows that for every odd $t$,

Thus $t\wedge o(g)=1$, so

In particular, for $t=p_i$, where $p_i$ is an odd prime, $p_i\wedge 2^n{p}_1^{a_1}{p}_2^{a_2}\cdots p_l^{a_l}=1$, thus $a_i=0$. Therefore $p-1=2^a$, and

By Problem 1.3.42, since $p$ is prime, $a$ is a power of $2$, so that there is an integer $n\ge 0$ such that

Every quadratic nonresidue is a primitive root if and only if $p=2^{2^n}+1$ for some integer $n\ge 0$. □