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.

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

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

1 Answer 1

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.

share|improve this answer
    
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
show 3 more comments

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.