# Conjectured primality test for specific class of $N=4kp^n+1$

Can you provide a proof or counterexample for the following claim?

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$N= 4kp^{n}+1$$ where $$k$$ is a positive natural number , $$4k<2^n$$ , $$p$$ is a prime number 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=P_p(S_{i-1})$$ with $$S_0$$ equal to the modular $$P_{kp^2}(a)\phantom{5} \text{mod} \phantom{5} N$$. Then $$N$$ is prime if and only if $$S_{n-2} \equiv 0 \pmod{N}$$ .

You can run this test here.

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

Further generalization of the claim

A

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$N= 2kp^{n} + 1$$ where $$k$$ is a positive natural number , $$2k<2^n$$ , $$p$$ is a prime number 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=P_p(S_{i-1})$$ with $$S_0$$ equal to the modular $$P_{kp^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.

B

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$N= 2kp^{n} - 1$$ where $$k$$ is a positive natural number , $$2k<2^n$$ , $$p$$ is a prime number 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=P_p(S_{i-1})$$ with $$S_0$$ equal to the modular $$P_{kp^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.

The "if and only if" statement fails for $$[p,n,k,a] \in \{ [3, 4, 1, 100], [3, 4, 1, 225], [3, 6, 13, 2901] \}$$ and many others. In these cases, $$N$$ is not prime, but the congruence $$S_{n-2}\equiv 0\pmod{N}$$ still holds.