Primality test for specific class of $N=8k \cdot 3^n-1$

Question

This question is related to my previous question.

Can you prove or disprove the following claim:

Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$

Let $N=8k \cdot 3^n-1$ such that $n>2$ , $k>0$ , $8k <3^n$ and

$\begin{cases} k \equiv 1 \pmod{5} \text{ with } n \equiv 0,1 \pmod{4} \\ k \equiv 2 \pmod{5} \text{ with } n \equiv 1,2 \pmod{4} \\ k \equiv 3 \pmod{5} \text{ with } n \equiv 0,3 \pmod{4} \\ k \equiv 4 \pmod{5} \text{ with } n \equiv 2,3 \pmod{4} \end{cases}$

Let $S_i=S_{i-1}^3-3S_{i-1}$ with $S_0=P_{18k}(3)$ , then $N$ is prime iff $S_{n-2} \equiv 0 \pmod N$ .

You can run this test here. I have verified this claim for $k \in [1,300]$ with $n \in [3,1000]$ .

Answer 1

Assume that $N$ is prime. Then we prove $S_{n-2}\equiv 0\pmod N$, the assumption that $8k<3^n$ is not used. I do not know how to prove it in the opposite direction.

We have $P_m(2\cos t)=2\cos mt$, so they are Chebyshev polynomials and satisfy $P_{mn}=P_n\circ P_m$. Note that $x^3-3x=P_3$, thus $S_{i}=P_{18k\cdot 3^i}(3)$, $S_{n-2}=P_{2k\cdot 3^n}(3)=P_{(N+1)/4}(3)=P_{(N+1)/2}(\sqrt{5})$.

We prove that $2^{3(N+1)/2}P_{(N+1)/2}(\sqrt{5})$ is divisible by $N$ in the ring $\mathbb{Z}[\sqrt{5}]$. This would imply $$\frac{2^{3(N+1)/2}P_{(N+1)/2}(\sqrt{5})}N\in \mathbb{Z}[\sqrt{5}]\cap \mathbb{Q}=\mathbb{Z},$$ thus $N$ indeed divides $P_{(N+1)/2}(\sqrt{5})$. Further we write congruences modulo $N$ in the ring $\mathbb{Z}[\sqrt{5}]$.

Using quadratic reciprocity and the explicit calculations of powers of 3 modulo 4, we see that your additional condition means that 5 is a quadratic non-residue modulo $N$. This means that $5^{(N-1)/2}\equiv -1$, or $5^{N/2}\equiv-\sqrt{5}$. We have $$ 2^{3(N+1)/2}P_{(N+1)/2}(\sqrt{5})=2^{N+1}\left(\left(\sqrt{5}+1\right)^{(N+1)/2}+\left(\sqrt{5}-1\right)^{(N+1)/2}\right)\\ =\left(\sqrt{5}-1\right)^{(N+1)/2}\cdot\left( \left(\sqrt{5}+1\right)^{N+1}+2^{N+1}\right)\\ \equiv\left(\sqrt{5}-1\right)^{(N+1)/2}\cdot\left( (\sqrt{5}+1)(5^{N/2}+1)+2^{N+1}\right)\\\equiv \left(\sqrt{5}-1\right)^{(N+1)/2}\cdot\left( (\sqrt{5}+1)(1-\sqrt{5})+2^{N+1}\right)\equiv 0. $$