This question is successor of Compositeness test for specific class of $N=k \cdot b^n-1$ .

Can you provide a proof or a counterexample to the following claim :

Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ . Let $N=k \cdot b^n-1$ such that $k>0$ , $3 \not\mid k$ , $k<2^n$ , $b>0$ , $b$ is even number, $3 \not\mid b$ and $n > 2$ . Let $S_i=P_b(S_{i-1})$ with $S_0=P_{kb/2}(P_{b/2}(4))$ , then if $S_{n-2} \equiv 0\pmod{N}$ then $N$ is a prime .

You can run this test here .

I have verified this claim for many random values of $k$ , $b$ and $n$ .


A command line program that implements this test can be found here .

  • 1
    $\begingroup$ When $b=2$ this looks pretty close to the Riesel--Lucas--Lehmer test for primality of numbers of the form $k\cdot 2^n - 1$. See en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test. Note your $(4 \pm \sqrt{4^2-4})/2 = 2 \pm \sqrt{3}$. $\endgroup$ – KConrad Aug 27 '18 at 23:59
  • $\begingroup$ @KConrad Your observation is correct. I tried to generalize Riesel's theorem. $\endgroup$ – Peđa Terzić Aug 28 '18 at 4:38

Not a full answer (but maybe need to fill computational details): If I am not mistaken, you are using the group law of a conic $C$ to iterate a point $p_0$ by multiplication by $b$. In fact, $S_{n-2}$ is the $x$ coordinate of the point $b^{n-2}(kp_0)$ in $C$ of order $4$, therefore, $S_{n-1}$ of a point of order $2$ and finally $S_n$ for the $x$ coordinate of the identity of $C$. These $x$ coordinates are $0,-1,1$. If you find such a sequence (which corresponds to the iteration of a fixed point $kp_0$ by multiplication by $b$) then it means that $C(\mathbb{Z}/N)\cong \mathbb{Z}/(N+1)\mathbb{Z}=\mathbb{Z}/kb^n\mathbb{Z}$. Therefore prime. Your restriction $k<2^n$ I think can be $k<b^n$. I did not have time to calculate $C$ but it should be something doable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.