Primality test for numbers of the form $(3^p-1)/2$

Question

Here is my observation :

Let $N$ = $(3^p-1)/2$ when $p$ is a prime number $p > 3$

Let $S_i=S_{i-1}^3-3 S_{i-1}$ with $S_0=52$ . Then $N$ is prime if and only if $S_{p-1} \equiv S_{0}\pmod{N}$.

I choose 52 because this is one of the "seeds" for the test of Lucas-Lehmer and it seems it works with this "seed" (you can find the seeds for Lucas-Lehmer test here)

For example with $p$ = $7$ I found with Pari GP

 52, 1093
 548, 1093
 682, 1093
 969, 1093
 1033, 1093
 594, 1093
 52, 1093

And $1093$ is a prime number

I checked until $p=1100$ and I didn't find counterexample.

Is there a way to explain this ? I don't know how to start for proving it. If you found a counterexample please tell me.

Answer 1

Your sequence is $$S_i = (2+\sqrt3)^{3^{i+1}}+(2-\sqrt3)^{3^{i+1}}$$ Proof: check that $S_0=52$ and $S_{i+1}=S_i^3-3S_i$.

So $S_{p-1}=S_0\bmod N$ iff $$(2+\sqrt3)^{3^p} +(2-\sqrt3)^{3^p}=(2+\sqrt3)^3+(2-\sqrt3)^3\bmod N$$

If $N$ is prime then

• $N=1\bmod 3$ so $1+\sqrt{-3}^N= (1+\sqrt{-3})^N=(2\zeta_3)^N=2 \zeta_3 =1+\sqrt{-3}\bmod N$

• $N=1\bmod 4$ so $\sqrt{3}^N = (-i\sqrt{-3})^N= (-i)^N \sqrt{-3}^N= -i \sqrt{-3}=\sqrt3\bmod N$

• $(2+\sqrt3)^N = 2^N+(\sqrt3)^N=2+\sqrt3\bmod N$

  Similarly $(2-\sqrt3)^N=2-\sqrt3\bmod N$

• And hence $$S_{p-1}=(2+\sqrt3)^{2N+1}+(2-\sqrt3)^{2N+1}=(2+\sqrt3)^3+ (2-\sqrt3)^3=S_0\bmod N$$

That's a good start. But for the other direction, I don't see why $S_{p-1}=S_0\bmod N$ would imply that $N$ is not composite.