13
$\begingroup$

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?

$\endgroup$
4
  • $\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$ Dec 31, 2012 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$ Dec 31, 2012 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$ Dec 31, 2012 at 13:00
  • 1
    $\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$ Dec 31, 2012 at 13:06

2 Answers 2

15
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Here's another elementary proof employing the binomial theorem.

Let $p=2^n+1$ be a Fermat prime for $n\geq 2$. Since $p\equiv 1\pmod{4}$, it is known that $a$ is a primitive root mod $p$ iff $-a$ is a primitive root mod $p$ (in fact, this is exercise $4$, chapter $4$, of Ireland and Rosen's Number Theory). We will show that $-3$ is a primitive root for $p$.

First, notice that $$-3\equiv 2^n-2\equiv 2(2^{n-1}-1)\equiv 2(2^{n-1}+2^n)\pmod{p}.$$ Moreover, since $\phi(p)=2^n$, it suffices to show that $(-3)^{2^{n-1}}\not\equiv 1\pmod{p}$. Given that $2^{n-1}\geq n$, we have $$(-3)^{2^{n-1}}\equiv (-1)(2^{n-1}+2^n)^{2^{n-1}}\pmod{p}.$$ On the other hand, in the binomial expansion of $(2^{n-1}+2^n)^{2^{n-1}}$ we sum $[k(n-1)+(2^{n-1}-k)n]^{\text{th}}$ powers of $2$, for $k=0,1,\ldots,2^{n-1}$. Since, $$k(n-1)+(2^{n-1}-k)n=2^{n-1}n-k\geq 2^{n-1}(n-1)\geq n,$$ these powers of $2$ will all yield $-1\pmod{p}$. Therefore, $$(2^{n-1}+2^n)^{2^{n-1}}\equiv-\sum_{k=0}^{2^{n-1}}\binom{2^{n-1}}{k}\equiv-(1+1)^{2^{n-1}}\equiv 1\pmod{p}.$$ Thus, $(-3)^{2^{n-1}}\equiv -1\pmod{p}$, as desired.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .