Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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