The following is exercise 6 of Chapter 4 in Ireland and Rosen's Number Theory.
If $p=2^n+1$ is a Fermat prime, show that $3$ is a primitive root modulo $p$.
I first recall that any Fermat prime actually has form $2^{2^n}+1$. Hence $p\equiv 1\pmod{4}$. Exercise 4 from the same chapter states the if $p\equiv 1\pmod{4}$, then $a$ is a primitive root mod $p$ iff $-a$ is as well. I was able to prove this, but unable to show $-3$ is a primitive root.
Is there a fruitful approach?
P.S. I was able to cheat and use the fact that
$$
\phi(p-1)=\phi(2^{2^n})=2^{2^n-1}=(p-1)/2
$$
and since there are $(p-1)/2$ quadratic nonresides and each of the $\phi(p-1)$ primitive roots is a quadratic nonresidue, then the two sets are actually the same.
Then $3$ is a nonresidue since applying quadratic reciprocity
$$
\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)=\left(\frac{2}{3}\right)=-1
$$
hence not primitive. But I only know this from a number theory class I took back in school, not from anything in Ireland and Rosen so far. Is there a way to avoid using a sledgehammer the authors haven't given me yet?
Best Answer
I've tried to fill in some of the details if its helpful. Thanks to Geoff's comments.
First, assume that $p\neq 3$, otherwise the claim is not true. Recall that if $p\equiv 1\pmod{4}$, then $-1$ is a square. This follows, for by Wilson's theorem, we may write $$ -1\equiv (p-1)!\equiv \prod_{j=1}^{(p-1)/2} j(p-j)\equiv \prod_{j=1}^{(p-1)/2}-j^2\equiv (-1)^{\frac{p-1}{2}}\left(\prod_{j=1}^{(p-1)/2}j\right)^2\pmod{p}. $$ Since $p\equiv 1\pmod{4}$, it follows that $(-1)^{(p-1)/2}\equiv 1\pmod{p}$, and thus $\prod_{j=1}^{(p-1)/2}j$ is a square root of $-1$ modulo $p$.
I claim that $3$ is not a square modulo $p$. If not, since $p$ is a Fermat prime greater that $3$, $p\equiv 1\pmod{4}$, so $-1$ is a square, thus $-3$ is a square modulo $p$. Then we can write $-3\equiv (2x+1)^2\pmod{p}$. We can write $-3$ as the square of an odd, since if $-3$ is the square of an even, then $-3\equiv (2x)^2\equiv (2x+p)^2\pmod{p}$, where $2x+p$ is odd. But then \begin{align*} -3\equiv (2x+1)^2 &\implies 4x^2+4x+4\equiv 0\\ &\implies x^2+x+1\equiv 0\\ &\implies (x-1)(x^2+x+1)\equiv 0\\ &\implies x^3\equiv 1\\ \end{align*} where the second implication follows since $4$ is a unit modulo $p$. But $x\neq 1$, else we find $-3\equiv 9\pmod{p}$, which implies $12\equiv 0\pmod{p}$, which is false since $p$ is a Fermat prime greater than $3$. So $x$ has order dividing $3$, and thus has order $3$. Since $x^{p-1}\equiv 1\pmod{p}$, it follows that $3\mid p-1$, or $p\equiv 1\pmod{3}$, a contradiction since $p\equiv 2^n+1\equiv (-1)^n+1\equiv 0,2\pmod{3}$. (In fact it is necessarily congruent to $2$ since $p$ actually has form $2^{2^m}+1$.)
So $3$ is not a square modulo $p$. If $g$ is primitive root, then $3\equiv g^k\pmod{p}$, where $k$ is necessarily odd. Then if $\ell$ is such that, $$ 3^{\ell}\equiv g^{\ell k}\equiv 1\pmod{p} $$ we find $p-1\mid\ell k$. But $p-1=2^n$, and since $k$ is odd, it follows that $p-1\mid\ell$. So the order of $3$ is $p-1$, and so $3$ is a primitive root.