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

  • $\begingroup$ Is double $i-1$ typo? $\endgroup$ – joro Jun 5 '20 at 9:02
  • $\begingroup$ @joro No, it isn't. $\endgroup$ – Peđa Terzić Jun 5 '20 at 9:16
  • $\begingroup$ Where does this question come from and why do you expect this to be true? $\endgroup$ – Fedor Petrov Aug 23 '20 at 7:51
  • $\begingroup$ @FedorPetrov I made it by myself. I was inspired by Lucas-Lehmer-Riesel primality test. $\endgroup$ – Peđa Terzić Aug 23 '20 at 8:05

Assume that $N$ is prime. Then we prove $S_{n-2}\equiv 0\pmod N$, the assumption that $8k<3^n$ is not used. I do not know how to prove it in the opposite direction.

We have $P_m(2\cos t)=2\cos mt$, so they are Chebyshev polynomials and satisfy $P_{mn}=P_n\circ P_m$. Note that $x^3-3x=P_3$, thus $S_{i}=P_{18k\cdot 3^i}(3)$, $S_{n-2}=P_{2k\cdot 3^n}(3)=P_{(N+1)/4}(3)=P_{(N+1)/2}(\sqrt{5})$.

We prove that $2^{3(N+1)/2}P_{(N+1)/2}(\sqrt{5})$ is divisible by $N$ in the ring $\mathbb{Z}[\sqrt{5}]$. This would imply $$\frac{2^{3(N+1)/2}P_{(N+1)/2}(\sqrt{5})}N\in \mathbb{Z}[\sqrt{5}]\cap \mathbb{Q}=\mathbb{Z},$$ thus $N$ indeed divides $P_{(N+1)/2}(\sqrt{5})$. Further we write congruences modulo $N$ in the ring $\mathbb{Z}[\sqrt{5}]$.

Using quadratic reciprocity and the explicit calculations of powers of 3 modulo 4, we see that your additional condition means that 5 is a quadratic non-residue modulo $N$. This means that $5^{(N-1)/2}\equiv -1$, or $5^{N/2}\equiv-\sqrt{5}$. We have $$ 2^{3(N+1)/2}P_{(N+1)/2}(\sqrt{5})=2^{N+1}\left(\left(\sqrt{5}+1\right)^{(N+1)/2}+\left(\sqrt{5}-1\right)^{(N+1)/2}\right)\\ =\left(\sqrt{5}-1\right)^{(N+1)/2}\cdot\left( \left(\sqrt{5}+1\right)^{N+1}+2^{N+1}\right)\\ \equiv\left(\sqrt{5}-1\right)^{(N+1)/2}\cdot\left( (\sqrt{5}+1)(5^{N/2}+1)+2^{N+1}\right)\\\equiv \left(\sqrt{5}-1\right)^{(N+1)/2}\cdot\left( (\sqrt{5}+1)(1-\sqrt{5})+2^{N+1}\right)\equiv 0. $$

  • $\begingroup$ I guess the same reasoning can be applied here. $\endgroup$ – Peđa Terzić Aug 23 '20 at 8:07
  • $\begingroup$ Yes, it looks so. But again only in one direction. $\endgroup$ – Fedor Petrov Aug 23 '20 at 9:02

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.