# Conjectured primality tests for specific classes of $k\cdot b^n \pm 1$

Can you provide proofs or counterexamples for the claims given below?

Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following two claims:

First claim

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$M= k \cdot b^{n}-1$$ where $$k$$ is positive natural number , $$k<2^n$$ , $$b$$ is an even positive natural number and $$n\ge3$$ . Let $$a$$ be a natural number greater than two such that $$\left(\frac{a-2}{M}\right)=1$$ and $$\left(\frac{a+2}{M}\right)=-1$$ where $$\left(\frac{}{}\right)$$ denotes Jacobi symbol. Let $$S_i=P_b(S_{i-1})$$ with $$S_0$$ equal to the modular $$P_{kb/2}(P_{b/2}(a))\phantom{5} \text{mod} \phantom{5} M$$. Then $$M$$ is prime if and only if $$S_{n-2} \equiv 0 \pmod{M}$$ .

You can run this test here .

Second claim

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$N= k \cdot b^{n}+1$$ where $$k$$ is positive natural number , $$k<2^n$$ , $$b$$ is an even positive natural 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_b(S_{i-1})$$ with $$S_0$$ equal to the modular $$P_{kb/2}(P_{b/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 tested these claims for many random values of $$k$$, $$b$$ and $$n$$ and there were no countereamples.

EDIT

It is possible to reformulate these claims into more compact form:

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$N= k \cdot b^{n}\pm 1$$ where $$k$$ is positive natural number , $$k<2^n$$ , $$b$$ is an even positive natural number and $$n\ge3$$ . Let $$a$$ be a natural number greater than two such that $$\left(\frac{2-a}{N}\right)=\left(\frac{a+2}{N}\right)=-1$$ where $$\left(\frac{}{}\right)$$ denotes Jacobi symbol. Let $$S_i=P_b(S_{i-1})$$ with $$S_0$$ equal to the modular $$P_{kb/2}(P_{b/2}(a))\phantom{5} \text{mod} \phantom{5} N$$. Then $$N$$ is prime if and only if $$S_{n-2} \equiv 0 \pmod{N}$$ .