# Primality test for numbers of the form $N=4 \cdot 3^n-1$

Can you provide proof or counterexample for the claim given below?

Inspired by Lucas-Lehmer primality test I have formulated the following claim:

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$N= 4 \cdot 3^{n}-1$$ where $$n\ge3$$ . Let $$S_i=S_{i-1}^3-3 S_{i-1}$$ with $$S_0=P_9(6)$$ . Then $$N$$ is prime if and only if $$S_{n-2} \equiv 0 \pmod{N}$$ .

You can run this test here .

Numbers $$n$$ such that $$4 \cdot 3^n-1$$ is prime can be found here .

I was searching for counterexample using the following PARI/GP code:

CE431(n1,n2)=
{
for(n=n1,n2,
N=4*3^n-1;
S=2*polchebyshev(9,1,3);
ctr=1;
while(ctr<=n-2,
S=Mod(2*polchebyshev(3,1,S/2),N);
ctr+=1);
if(S==0 && !ispseudoprime(N),print("n="n)))
}


This answer proves that if $$N$$ is prime, then $$S_{n-2}\equiv 0\pmod N$$.

Proof :

First of all, let us prove by induction on $$i$$ that $$S_i=s^{2\cdot 3^{i+2}}+t^{2\cdot 3^{i+2}}\tag1$$ where $$s=\sqrt 2-1,t=\sqrt 2+1$$ with $$st=1$$.

We see that $$(1)$$ holds for $$i=0$$ since $$S_0=P_9(6)=(3-2\sqrt 2)^9+(3+2\sqrt 2)^9=s^{2\cdot 3^2}+t^{2\cdot 3^2}$$

Supposing that $$(1)$$ holds for $$i$$ gives \begin{align}S_{i+1}&=S_i^3-3S_i \\\\&=(s^{2\cdot 3^{i+2}}+t^{2\cdot 3^{i+2}})^3-3(s^{2\cdot 3^{i+2}}+t^{2\cdot 3^{i+2}}) \\\\&=s^{2\cdot 3^{i+3}}+t^{2\cdot 3^{i+3}}\qquad\square\end{align}

Using $$(1)$$ and $$N=4\cdot 3^n-1$$, we get $$S_{n-2}=s^{2\cdot 3^{n}}+t^{2\cdot 3^{n}}=s^{(N+1)/2}+t^{(N+1)/2}$$

So, we have, by the binomial theorem, \begin{align}&S_{n-2}^2-2 \\\\&=s\cdot s^{N}+t\cdot t^{N} \\\\&=(\sqrt 2-1)(\sqrt 2-1)^N+(\sqrt 2+1)(\sqrt 2+1)^N \\\\&=\sqrt 2\sum_{i=0}^{N}\binom Ni(\sqrt 2)^i((-1)^{N-i}+1^{N-i}) \\&\qquad\quad +\sum_{i=0}^{N}\binom Ni(\sqrt 2)^i(1^{N-i}-(-1)^{N-i}) \\\\&=\sum_{j=1}^{(N+1)/2}\binom N{2j-1}2^{j+1}+\sum_{j=0}^{(N-1)/2}\binom{N}{2j}2^{j+1}\end{align}

Using that $$\binom{N}{m}\equiv 0\pmod N$$ for $$1\le m\le N-1$$, we get $$S_{n-2}^2-2\equiv 2^{\frac{N+1}{2}+1}+2=4\cdot 2^{\frac{N-1}{2}}+2\pmod N\tag 2$$

Here, since $$4\cdot 3^{2k}-1\equiv 4\cdot 9^k-1\equiv 3\pmod 8$$ and $$4\cdot 3^{2k+1}-1\equiv 12\cdot 9^k-1\equiv 3\pmod 8$$ we see that $$N\equiv 3\pmod 8$$ from which we have $$2^{\frac{N-1}{2}}\equiv \left(\frac 2N\right)=(-1)^{(N^2-1)/8}=-1\pmod N\tag3$$ where $$\left(\frac{q}{p}\right)$$ denotes the Legendre symbol.

From $$(2)(3)$$, we have $$S_{n-2}^2-2\equiv 4\cdot (-1)+2\pmod N$$ from which $$S_{n-2}\equiv 0\pmod N$$ follows.$$\quad\blacksquare$$