# Primality test for specific class of $N=8kp^n-1$

My following question is related to my question here

Can you provide a proof or a counterexample for 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=8kp^n-1$$ such that $$k>0$$ , $$3 \not\mid k$$ , $$p$$ is a prime number, $$p \neq 3$$ , $$n > 2$$ and $$8k . Let $$S_i=P_p(S_{i-1})$$ with $$S_0=P_{2kp^2}(4)$$ , then: $$N \text{ is a prime iff } S_{n-2} \equiv 0\pmod{N}$$

You can run this test here.

EDIT

I have verified this claim for $$k \in [1,500]$$ with $$p \leq 139$$ and $$n \in [3,50]$$ .

• I think you should refer this question to that your new one. – zeraoulia rafik May 27 at 15:31
• P_m(x) = D_m(x,1) (the m-th Dickson polynomial of the first kind with parameter 1), so P_a(P_b) = P_{ab}, so S_0 = D_{(N+1)/4}(4,1) mod N. You might want to check out the literature on Dickson pseudoprimes. – Ben Smith May 28 at 10:45

This answer proves that if $$N$$ is a prime, then $$S_{n-2}\equiv 0\pmod N$$.
It can be proven by induction that $$S_i=(2-\sqrt 3)^{2kp^{i+2}}+(2+\sqrt 3)^{2kp^{i+2}}\tag1$$
Using $$(1)$$ and $$2\pm\sqrt 3=\bigg(\frac{\sqrt{6}\pm\sqrt 2}{2}\bigg)^2$$, we get \begin{align}&2^{N+1}S_{n-2}^2-2^{N+2} \\\\&=(\sqrt 6-\sqrt 2)(\sqrt 6-\sqrt 2)^{N}+(\sqrt 6+\sqrt 2)(\sqrt 6+\sqrt 2)^{N} \\\\&=\sqrt 6\bigg((\sqrt 6+\sqrt 2)^{N}+(\sqrt 6-\sqrt 2)^{N}\bigg) \\&\qquad\qquad +\sqrt 2\bigg((\sqrt 6+\sqrt 2)^{N}-(\sqrt 6-\sqrt 2)^{N}\bigg) \\\\&=\sqrt 6\sum_{i=0}^{N}\binom Ni(\sqrt 6)^{N-i}\bigg((\sqrt 2)^i+(-\sqrt 2)^i\bigg) \\&\qquad\qquad +\sqrt 2\sum_{i=0}^{N}\binom Ni(\sqrt 6)^{N-i}\bigg((\sqrt 2)^i-(-\sqrt 2)^i\bigg) \\\\&=\sum_{j=0}^{(N-1)/2}\binom N{2j}6^{(N+1-2j)/2}\cdot 2^{j+1}+\sum_{j=1}^{(N+1)/2}\binom N{2j-1}6^{(N-2j+1)/2}\cdot 2^{1+j} \\\\&\equiv 6^{(N+1)/2}\cdot 2+2^{(N+3)/2}\pmod N \\\\&\equiv 12\cdot 2^{(N-1)/2}\cdot 3^{(N-1)/2}+4\cdot 2^{(N-1)/2}\pmod N \\\\&\equiv 12\cdot (-1)^{(N^2-1)/8}\cdot \frac{(-1)^{(N-1)/2}}{\bigg(\frac N3\bigg)}+4\cdot (-1)^{(N^2-1)/8}\pmod N \\\\&\equiv 12\cdot 1\cdot \frac{-1}{1}+4\cdot 1\pmod N \\\\&\equiv -8\pmod N\end{align}
So, we get $$2^{N+1}S_{n-2}^2-2^{N+2}\equiv -8\pmod N$$ It follows from $$2^{N-1}\equiv 1\pmod N$$ that $$S_{n-2}\equiv 0\pmod N$$