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}$ .

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.