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

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 .

• You are unlikely to get much interest in this question. There are infinitely many possible conjectures in the world. What makes one interesting is its inherent beauty, its relation to existing work, and partial results in support of it. You have not demonstrated any of these, and yet you're asking strangers to spend hours of their time investigating your conjectures. 100 internet points is unlikely to make much difference. I recommend instead expanding the question substantially, giving partial proofs in support of your conjecture, and details about the "many random" choices you tested. – vadim123 Feb 4 at 19:47