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

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]$$ .

• Is double $i-1$ typo? – joro Jun 5 '20 at 9:02
• @joro No, it isn't. – Peđa Terzić Jun 5 '20 at 9:16
• Where does this question come from and why do you expect this to be true? – Fedor Petrov Aug 23 '20 at 7:51
• @FedorPetrov I made it by myself. I was inspired by Lucas-Lehmer-Riesel primality test. – Peđa Terzić Aug 23 '20 at 8:05

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.$$