# Is $17$ primitive root modulo $F_n(6)$?

Is it true that :

$17$ is primitive root modulo $F_n(6)$

where $F_n(6)$ is generalized Fermat prime of the form:

$F_n(6) =6^{2^n}+1 , ~~ n \geq 0$

I know that one can use quadratic reciprocity to show that $a$ is primitive root modulo $p$ .

For example :

$F_n(20)=20^{2^n}+1 \equiv (-1)^{2^n}+1 \equiv 2 \pmod 3$

and we know that. $F_n(20) \equiv 1 \pmod 4~~$ therefore :

$\left( \frac{3}{F_n(20)}\right)=\left( \frac{F_n(20)}{3}\right)=\left(\frac{2}{3}\right)=-1$

so , $~~3~~$ is quadratic nonresidue mod $~~F_n(20)~~$ , and therefore :

$3$ is primitive root modulo $F_n(20)$ .

But , this proof strategy doesn't work in case when we want to find out if a $17$ is primitive root modulo $F_n(6)$ .

-
How do you get from "3 is a quadratic nonresidue mod $F_n(20)$" to "3 is a primitive root modulo $F_n(20)$"? –  Gerry Myerson Feb 2 '12 at 23:17

As with your previous question about primes of the form $6^{2^n}+1$, this might be true for a dumb reason. I'm not sure that there any such primes other than $7$, $37$ and $1297$, and your statement is true for all of these.

However, if there are any others, then $17$ is not a primitive root for them. You can see this by a quadratic reciprocity computation: For $n \geq 4$, we have $6^{2^n} +1 \equiv 6^{16 \times \mathrm{something}} +1 \equiv 1+1 \equiv 2 \mod 17$ and $\left( \frac{2}{17} \right ) =1$, so, by quadratic reciprocity, $\left( \frac{17}{6^{2^n}+1} \right)=1$. A quadratic residue is not a primitive root.

However, this is just because you got the details of the quadratic reciprocity computation wrong. If we use $5$ instead of $17$, then $\left( \frac{2}{5} \right ) =-1$ and we deduce that $5$ is a quadratic nonresidue for any prime of the form $6^{2^n}+1$. So a better question is whether $5$ should be a primitive root for such a prime.

The answer is that I don't think it necessarily should and I can't see anyway to fix this part of the argument. Remember the criterion: If $p$ is prime, then $a$ is a primitive root in $\mathbb{Z}/p$ if and only if, for each $q$ dividing $p-1$, we have that $a$ is not a $q$-th power in $\mathbb{Z}/p$.

For Fermat primes, this works beautifully. The only $q$ dividing $(2^{2^n}+1)-1$ is $2$, so any nonsquare is a primitive root, and we can use quadratic reciprocity to find nonsquares.

In your case, $(6^{2^n}+1)-1$ is divisible by $2$ and $3$. The quadratic reciprocity computation above shows that $5$ is not a square, but we also must determine whether it is a cube. For this, we would like to use cubic reciprocity. That means that we needs to write $6^{2^n}+1$ as $a^2+3b^2$.

Now, assuming that $6^{2^n}+1$ is prime, it is of the form $a^2+3b^2$, because every prime which is $1 \mod 3$ is of this form. But I do not see any way to control what $a$ and $b$ are.

-
So, if one could prove that 17 is primitive root modulo $F_n(6)$ this would imply that there are no more primes of the form : $F_n(6)$ besides : $7 , 37~$ and $~1297$.... –  pedja Feb 3 '12 at 5:37
$5$ isn't primitive root modulo $1297$.....$5^{144} \equiv 1 \pmod{1297}$ –  pedja Feb 3 '12 at 7:14
Ah, good catch. And, indeed, $5$ is a cube modulo $1297$: $179^3 \equiv 485^3 \equiv 633^3 \equiv 5 \mod 1297$. –  David Speyer Feb 3 '12 at 14:17
,Which theorem one should use in order to prove or disprove that $17$ is primitive root modulo $F_n(6)$ ? –  pedja Feb 3 '12 at 14:38
As I said, for $n \geq 4$, quadratic reciprocity shows that $17$ is a square mod $F_n(6)$, and hence not a primitive root. –  David Speyer Feb 3 '12 at 20:05