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.
REMARK
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}$ .
GUI application that implements these tests can be found here .
A command line program that implements these tests can be found here .
I've tried some examples, checking with simple Pari/gp code, and I was unable to find any counter-example. However, I tried few. Someone should run some complete check up to some maximum value for different cases.
Anyway, this is the following of what you already published some years ago. Still very interesting in my opinion. I like the way you define the Seed (S0). However, some explanation would help: Something like this "how the test works" for LLR (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test#How_the_test_works) would help.
I hope that someone with Math skills (that I do not have...) will have a look and will provide hints for a proof of these conjectures.
Maybe you should show for b=2 that P_2(x) is x^2-2 , linking this to LLT and LLR more clearly.
Regards,
Tony