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?

  • $\begingroup$ 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!) $\endgroup$ – Noomi Holloway Dec 31 '12 at 12:05
  • $\begingroup$ 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. $\endgroup$ – Geoff Robinson Dec 31 '12 at 12:15
  • $\begingroup$ 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}$? $\endgroup$ – Noomi Holloway Dec 31 '12 at 13:00
  • $\begingroup$ 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.$ $\endgroup$ – Geoff Robinson Dec 31 '12 at 13:06

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.