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

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

Inspired by Lucas-Lehmer-Riesel 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= k \cdot 3^{n}-1$$ where $$k$$ is a positive even natural number , $$k<2^n$$ and $$n\ge3$$ . Let $$a$$ be a natural number greater than two such that $$\left(\frac{a-2}{N}\right)=1$$ and $$\left(\frac{a+2}{N}\right)=-1$$ where $$\left(\frac{}{}\right)$$ denotes Jacobi symbol. Let $$S_i=S_{i-1}^3-3 S_{i-1}$$ with $$S_0$$ equal to the modular $$P_{9k/2}(a)\phantom{5} \text{mod} \phantom{5} N$$. Then $$N$$ is prime if and only if $$S_{n-2} \equiv -2 \pmod{N}$$ .

You can run this test here .

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

CEk31(k1,k2,n1,n2)=
{
forstep(k=k1,k2,[2],
for(n=n1,n2,
if(k<2^n,
N=k*3^n-1;
a=3;
while(!(kronecker(a-2,N)==1 && kronecker(a+2,N)==-1),a++);
S=Mod(2*polchebyshev(9*k/2,1,a/2),N);
ctr=1;
while(ctr<=n-2,
S=Mod(2*polchebyshev(3,1,S/2),N);
ctr+=1);
if(S==N-2 && !ispseudoprime(N),print("k="k,"n="n)))))
}


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

Proof :

Let us define $$s,t$$ as $$s:=\frac{a-\sqrt{a^2-4}}{2},\qquad t:=\frac{a+\sqrt{a^2-4}}{2}$$ where $$st=1$$.

Here, let us prove by induction on $$i$$ that $$S_i\equiv s^{3^{i+2}k/2}+t^{3^{i+2}k/2}\pmod N\tag1$$

We see that $$(1)$$ holds for $$i=0$$ since $$S_0\equiv P_{9k/2}(a)=s^{9k/2}+t^{9k/2}\pmod N$$ Supposing that $$(1)$$ holds for $$i$$ gives \begin{align}S_{i+1}& \equiv S_i^3-3S_i \\\\&\equiv (s^{3^{i+2}k/2}+t^{3^{i+2}k/2})^3-3(s^{3^{i+2}k/2}+t^{3^{i+2}k/2})\\\\&\equiv s^{3^{i+3}k/2}+t^{3^{i+3}k/2}\pmod N\quad\square\end{align}

Now, using $$(1)$$ and $$k\cdot 3^n=N+1$$, we get $$S_{n-2}\equiv s^{3^nk/2}+t^{3^nk/2}\equiv s^{(N+1)/2}+t^{(N+1)/2}\pmod N$$ Using that $$\sqrt{\frac{a\pm\sqrt{a^2-4}}{2}}=\frac{\sqrt{a+2}\pm\sqrt{a-2}}{2}$$ we have \begin{align}2^{N+1}S_{n-2}&\equiv (\sqrt{a+2}-\sqrt{a-2})^{N+1}+(\sqrt{a+2}+\sqrt{a-2})^{N+1} \\\\&\equiv (\sqrt{a+2}-\sqrt{a-2})(\sqrt{a+2}-\sqrt{a-2})^{N} \\&\qquad\quad +(\sqrt{a+2}+\sqrt{a-2})(\sqrt{a+2}+\sqrt{a-2})^{N} \\\\&\equiv \sqrt{a+2}\sum_{i=0}^{N}\binom Ni(\sqrt{a+2})^i((-\sqrt{a-2})^{N-i}+(\sqrt{a-2})^{N-i}) \\&\qquad \quad +\sqrt{a-2}\sum_{i=0}^{N}\binom Ni(\sqrt{a+2})^i((\sqrt{a-2})^{N-i}-(-\sqrt{a-2})^{N-i}) \\\\&\equiv \sum_{j=1}^{(N+1)/2}\binom{N}{2j-1}(a+2)^{j}\cdot 2(a-2)^{(N-(2j-1))/2} \\& \qquad \quad +\sum_{j=0}^{(N-1)/2}\binom{N}{2j}(a+2)^{j}\cdot 2(a-2)^{(N-2j+1)/2}\pmod N\end{align}

Using that $$\binom Nm\equiv 0\pmod N$$ for $$1\le m\le N-1$$, we get $$4\cdot 2^{N-1}S_{n-2}\equiv 2(a+2)(a+2)^{(N-1)/2}+2(a-2)(a-2)^{(N-1)/2}\pmod N$$

Since $$2^{N-1}\equiv 1,\qquad (a-2)^{(N-1)/2}\equiv 1,\qquad (a+2)^{(N-1)/2}\equiv -1\pmod N$$ we have $$4S_{n-2}\equiv -2(a+2)+2(a-2)\equiv -8\pmod N$$ from which $$S_{n-2}\equiv -2\pmod N$$ follows.$$\quad\blacksquare$$