Skip to main content
2 of 2
Improved latex formatting
Pedja
  • 2.7k
  • 15
  • 26

Primality test for specific class of $N=8k \cdot 3^n-1$

This question is related to my previous question.

Can you prove or disprove 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=8k \cdot 3^n-1$ such that $n>2$ , $k>0$ , $8k <3^n$ and

$\begin{cases} k \equiv 1 \pmod{5} \text{ with } n \equiv 0,1 \pmod{4} \\ k \equiv 2 \pmod{5} \text{ with } n \equiv 1,2 \pmod{4} \\ k \equiv 3 \pmod{5} \text{ with } n \equiv 0,3 \pmod{4} \\ k \equiv 4 \pmod{5} \text{ with } n \equiv 2,3 \pmod{4} \end{cases}$

Let $S_i=S_{i-1}^3-3S_{i-1}$ with $S_0=P_{18k}(3)$ , then $N$ is prime iff $S_{n-2} \equiv 0 \pmod N$ .

You can run this test here. I have verified this claim for $k \in [1,300]$ with $n \in [3,1000]$ .

Pedja
  • 2.7k
  • 15
  • 26