# Compositeness tests for numbers of the form $\frac{k \cdot b^n \pm 1}{2}$

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

First claim

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$M= \frac{k \cdot b^{n}-1}{2}$$ where $$k$$ is an odd positive natural number , $$k<2^n$$ , $$b$$ is an odd positive natural number greater than one 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}(a)\phantom{5} \text{mod} \phantom{5} M$$. Then, if $$M$$ is prime then $$S_{n-2} \equiv a \pmod{M}$$ .

Second claim

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$N= \frac{k \cdot b^{n}+1}{2}$$ where $$k$$ is an odd positive natural number , $$k<2^n$$ , $$b$$ is an odd positive natural number greater than one 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}(a)\phantom{5} \text{mod} \phantom{5} N$$. Then, if $$N$$ is prime then $$S_{n-2} \equiv a \pmod{N}$$ .

I have tested these claims for many random values of 𝑘, 𝑏 and 𝑛 and there were no counterexamples.