# Is it possible to prove that $3$ is a primitive root of any Fermat prime without quadratic reciprocity?

Browsing around online, I find a handful of proofs that $3$ is always a primitive root of any Fermat prime $2^n+1$. One particular proof is found in problems 4 and 5 here. Another proof I found on a page at SUNYSB makes use of Pepin's test whose proof seems to require quadratic reciprocity.

So out of curiosity, is it possible to prove that any Fermat prime has $3$ as a primitive root without use of quadratic reciprocity?

The few observations I do know is that if $2^n+1$ is prime for $n\gt 1$, then $n$ is actually a power of $2$, and that in this case $U(\mathbb{Z}/p\mathbb{Z})$ has order $2^n$, so the order of $3$ must also be a power of $2$, but I couldn't get much further than that.

-
Under the assumption that all the Fermat primes are known, you can just try them all... –  Ross Millikan Aug 7 '11 at 2:44
Eh, probably n should be >1? –  awllower Aug 19 '11 at 16:20
@awllower, oops, thanks. I'll fix that. –  yunone Aug 19 '11 at 16:39

## 2 Answers

Let $n$ denote the number $2^{2^{n'}}+1$, $g$ be a primitive root modulo $n$, and let $n(a)$ denote the order of $a$ modulo $n$, for an integer $a$. Since $a^{n(a)}\equiv g^{n-1} \pmod{n}$, if $n$ is a prime, $a\equiv g^{(n-1)/n(a)} \pmod{n}$; hence $a$ is a quadratic residue modulo $n$ if, and only if, (n-1)/n(a) is even. Take for $n$ the number $2^{2^{n'}}+1$, we see that $a$ is a quadratic residue modulo $n$ if and only if $a$ is not a primitive root modulo $n$.
As $2^{2^{n'}}+1\equiv 2 \pmod{3}$, for every $n'$>1, $n$ is of the form $3x+2$. If 3 is a quadratic residue modulo $n$, however, $n$ must divide a number of the form $x²-3y²$, hence $\equiv 1 \pmod{3}$, which is obviously a contradiction. Therefore 3 is not a quadratic residue modulo $n$, thus 3 is a primitive root modulo $n$.
Please forgive me for some typing error.
Thanks in any case for paying attention.

-
Thanks for your answer awllower. –  yunone Aug 19 '11 at 17:32
Always trying to help, and to be helped. –  awllower Aug 20 '11 at 3:55
You assume that $g$, as a primitive root, is not a quadratic residue, which is… what we're trying to show. Doesn't this create a loop? –  Andrey Vihrov Nov 17 '12 at 17:03
But $g^n$ is a quadratic residue if and only if $n$ is even. I cannot perceive why you said that this is what we want to show. Remark that there are exactly half of relatively prime numbers that are residues, which correspond just to those with even exponents. –  awllower Nov 19 '12 at 4:58
In addition, what we want to prove is that 3 is a primitive root, and we achieve this by showing that 3 is not a quadratic residue. –  awllower Nov 19 '12 at 4:59

Hint from Ireland/Rosen which avoids explicitly using quadratic reciprocity:

If $3$ is not a primitive element, show that $3$ is congruent to a square. Use exercise $4$ (which states that if $q$ is a prime and $q \equiv 1 \pmod{4}$, then $x$ is a quadratic residue $\bmod q$ if and only if $-x$ is a quadratic residue $\bmod{q}$) to show that there is a number $a$ such that $-3 \equiv a^2 \pmod{p}$. Now solve $2u \equiv - 1 + a \pmod{p}$ and show that $u$ has order $3$. This would imply that $p \equiv 1 \pmod{3}$, which cannot be true.

-
Thanks DJC, I'm going to try to work this out. –  yunone Aug 7 '11 at 3:10
Heh, I pretty slow, but I think I have something. If $3$ is not a primitive root, then $3$ has order $2^k$ for some $k\lt n$. By Proposition 4.2.1, $3$ is a quadratic residue iff $3^{\phi(p)/d}\equiv 1\pmod{p}$, but $d=(2,\phi(p))=(2,2^n)=2$. But $3^{2^n/2}=3^{2^{n-1}}\equiv 1\pmod{p}$ since $2^k|2^{n-1}$. By Exercise 4, $-3$ is a quadratic residue, so $-3\equiv a^2\pmod{p}$. Now $(2,p)=1$, so I want to solve $u\equiv (-1+a)/2\pmod{p}$. $u^2\equiv (-1-a)/2\pmod{p}$, but then $u^3\equiv (1-a^2)/4\equiv 1\pmod{p}$. I get a little lost seeing why $p\equiv 1\pmod{3}$. Is it because... –  yunone Aug 7 '11 at 3:56
if $u$ has order $3$ in the group of units, then $3|\phi(p)$, or $3|2^n$, a contradiction? So $3$ must actually be a primitive root. –  yunone Aug 7 '11 at 3:57
@yunone: Sorry for the slow response. I have solved this exercise, but I can't seem to be reconstructing the argument. I guess that means I didn't learn it well enough to begin with. I can't give this my undivided attention, but I'll let you know if I hammer out the details. –  JavaMan Aug 7 '11 at 21:06
Oh no, nothing to be sorry about. I don't ever expect anyone's undivided attention here. I'm fairly confident in my proof in the above comments, so please don't get hung up on this if you don't want to or don't have to the time. –  yunone Aug 7 '11 at 22:26