= Solution
<Euler's criterion> states that for an odd <prime number> $p$ and $p\nmid a$,
$$
\boxed{
a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p
},
$$
where the right-hand side is the <Legendre symbol>.
Let $g$ be a <primitive root> modulo $p$. Its <multiplicative order> is $p-1$, so $g^{(p-1)/2}\ne1$. This power has square $g^{p-1}=1$, and the only roots of $X^2-1$ modulo the odd prime $p$ are $\pm1$. Therefore
$$
g^{(p-1)/2}\equiv-1\pmod p.
$$
Euler's criterion now gives $(g/p)=-1$, so every primitive root is a <quadratic nonresidue>.
Now let $p=2^{2^k}+1$ be a <Fermat prime>, with $k\geq1$. The number of primitive roots modulo $p$ is
$$
\varphi(p-1)
=\varphi\left(2^{2^k}\right)
=2^{2^k-1}
=\frac{p-1}{2}.
$$
There are also exactly $(p-1)/2$ quadratic nonresidues. Since every primitive root is a nonresidue, these equally large sets coincide. Thus every quadratic nonresidue modulo $p$ is a primitive root, as summarized by <Quadratic nonresidues modulo a Fermat prime>.
Finally, $p\equiv1\pmod4$ and $p\equiv2\pmod3$. <Quadratic reciprocity> therefore gives
$$
\left(\frac3p\right)
=\left(\frac p3\right)
=\left(\frac23\right)
=-1.
$$
Hence $3$ is a quadratic nonresidue modulo $p$, and consequently
$$
\boxed{3\text{ is a primitive root modulo every Fermat prime }p
\text{ with }k\geq1}.
$$
Back to article page
