10
$\begingroup$

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.

  • 0
    Under the assumption that all the Fermat primes are known, you can just try them all...2011-08-07
  • 0
    Eh, probably n should be >1?2011-08-19
  • 0
    @awllower, oops, thanks. I'll fix that.2011-08-19

2 Answers 2

3

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^2-3y^2$, 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.

  • 0
    Thanks for your answer awllower.2011-08-19
  • 0
    Always trying to help, and to be helped.2011-08-20
  • 0
    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?2012-11-17
  • 0
    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.2012-11-19
  • 0
    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.2012-11-19
4

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.

  • 0
    Thanks DJC, I'm going to try to work this out.2011-08-07
  • 0
    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...2011-08-07
  • 0
    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.2011-08-07
  • 0
    @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.2011-08-07
  • 0
    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.2011-08-07
  • 0
    But the exercise 4 is a mere variant of the quadratic reciprocity(the supplementary law); indeed it should not use the law to calculate the Legendre symbol, appearing not so easy to forget!! At least it provides a way...2011-08-19
  • 0
    I'm confused about one step. How does exercise 4 show that 3 being a quadratic residue implies that -3 is also quadratic residue?2013-01-10