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)$ .

  • 1
    $\begingroup$ How do you get from "3 is a quadratic nonresidue mod $F_n(20)$" to "3 is a primitive root modulo $F_n(20)$"? $\endgroup$ – 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.

  • $\begingroup$ 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$.... $\endgroup$ – Peđa Terzić Feb 3 '12 at 5:37
  • $\begingroup$ $5$ isn't primitive root modulo $1297$.....$5^{144} \equiv 1 \pmod{1297}$ $\endgroup$ – Peđa Terzić Feb 3 '12 at 7:14
  • $\begingroup$ Ah, good catch. And, indeed, $5$ is a cube modulo $1297$: $179^3 \equiv 485^3 \equiv 633^3 \equiv 5 \mod 1297$. $\endgroup$ – David E Speyer Feb 3 '12 at 14:17
  • $\begingroup$ ,Which theorem one should use in order to prove or disprove that $17$ is primitive root modulo $F_n(6)$ ? $\endgroup$ – Peđa Terzić Feb 3 '12 at 14:38
  • $\begingroup$ 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. $\endgroup$ – David E Speyer Feb 3 '12 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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