# $GF(n,6)$ is prime iff : $GF(n,6) \mid S_n$?

Let us define recurrence equation as :

$S_n=S^3_{n-1}-3\cdot S_{n-1}$ , with $S_0=52$

and let us define following notation :

$GF(n,6)=6^{2^n}+1$

I have noticed that :

$GF(1,6) \mid S_1$ , $GF(2,6) \mid S_2$ , $GF(3,6) \nmid S_3$ , $GF(4,6) \nmid S_4$

So my assumption is that :

$GF(n,6)$ is prime iff : $GF(n,6) \mid S_n$ , where $n>0$

Any idea how to prove or disprove this statement ?

$GF(5,6) \nmid S_5$ , $GF(6,6) \nmid S_6$ , $GF(7,6) \nmid S_7$ , $GF(8,6) \nmid S_8$

-
I would want to see more than 4 examples before I made any guesses. –  Gerry Myerson Jan 26 '12 at 11:02
@GerryMyerson,Primes of the form : $GF(n,6)$ are very rare... –  pedja Jan 26 '12 at 11:07
Undoubtedly. So? –  Gerry Myerson Jan 26 '12 at 11:11
@GerryMyerson,In fact, I don't think that there is any known larger prime of the form $GF(n,6)$ than $GF(2,6)$...so how can I provide more examples ? –  pedja Jan 26 '12 at 11:18
You can provide more examples where the number is not prime, and the divisibility relation does not hold. –  Gerry Myerson Jan 26 '12 at 12:32

I find this a bizarre way to present the question. Did pedja honestly just guess this recursion? It seems to me far more likely that he found this criterion somewhere and would like to know whether it works.

In any case, this is probably true because both events are very rare, and it is quite plausible that neither one happens for $n>2$. However, I don't think that checking either criterion proves the other. This looks like it is attempting to be a variant of Pepin's test and the Lucas-Lehmer test, so I originally assumed that it would work for the same reasons. However, when I tried to mimic those proofs, I found that I wasn't testing the right things.

Set $\theta = 26+15 \sqrt{3}$. Note that $\theta^{-1} = 26-15 \sqrt{3}$. We claim that $$S_n = \theta^{3^n} + \theta^{-3^n}.$$ Proof: This is true for $n=0$, and is easily checked to obey the relevant recursion.

For future use, we note that $$26+15 \sqrt{3} = (2+\sqrt{3})^3 = (\zeta+2+\zeta^{-1})^3 = (\eta + \eta^{-1})^6$$ where $\zeta$ and $\eta$ are primitive $12$th and $24$th roots of unity.

Suppose that $GF(n,6)$ is prime: Write $GF(n,6) =p$. Then, for $n >2$, we have $p \equiv 1 \mod 24$, so there is a $24$th root of unity in $\mathbb{F}_p$. Call it $\eta$. Then we have $S_n = (\eta+\eta^{-1})^{6 \cdot 3^n} + (\eta+\eta^{-1})^{-6 \cdot 3^n}$. We see that $p | S_n$ if and only if $(\eta+\eta^{-1})^{12 \cdot 3^n} = -1$.

Is there a reason to expect this to be true? I don't see one. The unit group of $\mathbb{F}_p$ is cyclic of order $p-1 = 6^{2^n}$. So, for most members of this group, $12 \cdot 6^n$ is not nearly enough to make them become $2$-torsion. It would be more natural to have a criterion where something got raised to the $6^{2^n}$ power, not the $(\mathrm{constant} \cdot 3^n)$ power. Of course it might happen that $\eta+ \eta^{-1}$ has the right order for this to work out, but I see no reason that it should.

Suppose that $GF(6,n) | S_n$: I also don't see why this implies that $GF(6,n)$ is prime. Write $N = GF(6,n)$. For simplicity, let's assume that we at least know that all of the prime factors of $N$ are $1 \mod 24$; even in this case, I can't see how to show that $N$ is prime.

The hypothesis on the prime factors of $N$ tells you that there is an element $\eta$ in $(\mathbb{Z}/N)^{\ast}$ with order $24$. As before, we have $(\eta+\eta^{-1})^{12 \cdot 3^n} = -1$. This tells us very little about $(\mathbb{Z}/N)^{\ast}$.

If we imposed that $N$ did not divide $S_{n-1}$, then we would at least know that $(\eta+\eta^{-1})^{12 \cdot 3^n} = -1$ and $(\eta+\eta^{-1})^{12 \cdot 3^{n-1}} \neq -1$. So we would know that the unit group of $(\mathbb{Z}/N)^{\ast}$ contained a cyclic subgroup of order $24 \cdot 3^n$. That's a pretty strong condition, but it isn't nearly strong enough to force $N$ to be prime -- for that, we need a cyclic subgroup of order $6^{2^n}$.

If we don't assume that the prime factors of $N$ are $1 \mod 24$, then we should be able to draw some sort of more complicated conclusion by thinking about fields of prime power order, but I didn't think it through.

Conclusion: Let's say that a number is $6$-powerish if it is of the form $2^a 3^b$. Suppose that all of the prime factors of $S_n$ are $1 \mod 24$, so that there is a primitive $24$-th root of unity $\eta$ modulo $n$.

Then both conditions are saying something about the order of $\eta+\eta^{-1}$ being $6$-powerish. It is quite plausible that the order of $\eta+ \eta^{-1}$ is NOT $6$-powerish for any $n>3$, and that both conditions are simply always false. However, the precise statements that they are making about the order of $\eta+ \eta^{-1}$ are different.

-
,You are right...I didn't guess this recurrence equation .I have deduced it from closed form expression...On the other hand I haven't found this criterion somewhere..My idea was to find sequence which is similar to the Lucas sequence : $S_n=S^2_{n-1}-2$ –  pedja Jan 26 '12 at 15:19
A good, thorough, analysis. –  Gerry Myerson Jan 26 '12 at 23:38
Maybe statement should be : $GF(n,6) \mid S_{2^{n-1}}$ –  pedja Jan 27 '12 at 8:25
But you still wind up raising $\eta+\eta^{-1}$ to the $(\mathrm{constant}) \times 3^{\mathrm{big number}}$ power, not $6^{2^n}$. –  David Speyer Jan 27 '12 at 12:16
@DavidSpeyer,recently I have found quartic recurrence equation such that $GF(n,4) \mid S_{2^n-1}$ .I have proved correctness of this criterion .Also, if we take $S_0=4$ then $GF(n,6) \mid S_{2^{n-1}+1}$.... –  pedja Jan 27 '12 at 12:32