# Elementary proof that $3$ is a primitive root of a Fermat prime?

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?

-
I just noticed a similar question in the related section, but I don't follow the accepted answer, and the second is incomplete. Please don't close as a duplicate! (Sorry!) – Noomi Holloway Dec 31 '12 at 12:05
Well, Javaman's answer there does answer this question : $3$ must not be a square $(mod p)$, otherwise $-3$ is a square and $p \equiv 1$ (mod $3$). Also, you do need $p >3,$ as $3$ is a Fermat prime. – Geoff Robinson Dec 31 '12 at 12:15
Thanks @GeoffRobinson, but how does $3$ being a square imply $-3$ is a square, and how in turn does that imply $p\equiv 1\pmod{3}$? – Noomi Holloway Dec 31 '12 at 13:00
Well, because $p \equiv 1$ (mod 4), -1 is a square (mod $p$)- easy and done in many textbooks. It was covered in Javaman's answer, but (as was known to Gauss), if we write $(2x+1)^{2} = -3$ (mod p), then we have $x^{2}+x+1 = 0$ and then $x^{3}-1= 0$ mod $p$, but $x \neq 1$, so $3$ divides $p-1.$ – Geoff Robinson Dec 31 '12 at 13:06

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.