My following question is related to my question here

Can you provide a proof or a counterexample for 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=8kp^n-1$ such that $k>0$ , $3 \not\mid k$ , $p$ is a prime number, $p \neq 3$ , $n > 2$ and $8k<p^n$ . Let $S_i=P_p(S_{i-1})$ with $S_0=P_{2kp^2}(4)$ , then: $$N \text{ is a prime iff } S_{n-2} \equiv 0\pmod{N}$$

You can run this test here.


I have verified this claim for $k \in [1,500]$ with $p \leq 139$ and $n \in [3,50]$ .

  • 1
    $\begingroup$ I think you should refer this question to that your new one. $\endgroup$ – zeraoulia rafik May 27 at 15:31
  • 2
    $\begingroup$ P_m(x) = D_m(x,1) (the m-th Dickson polynomial of the first kind with parameter 1), so P_a(P_b) = P_{ab}, so S_0 = D_{(N+1)/4}(4,1) mod N. You might want to check out the literature on Dickson pseudoprimes. $\endgroup$ – Ben Smith May 28 at 10:45

This is a partial answer.

This answer proves that if $N$ is a prime, then $S_{n-2}\equiv 0\pmod N$.

Proof :

It can be proven by induction that $$S_i=(2-\sqrt 3)^{2kp^{i+2}}+(2+\sqrt 3)^{2kp^{i+2}}\tag1$$

Using $(1)$ and $2\pm\sqrt 3=\bigg(\frac{\sqrt{6}\pm\sqrt 2}{2}\bigg)^2$, we get $$\begin{align}&2^{N+1}S_{n-2}^2-2^{N+2} \\\\&=(\sqrt 6-\sqrt 2)(\sqrt 6-\sqrt 2)^{N}+(\sqrt 6+\sqrt 2)(\sqrt 6+\sqrt 2)^{N} \\\\&=\sqrt 6\bigg((\sqrt 6+\sqrt 2)^{N}+(\sqrt 6-\sqrt 2)^{N}\bigg) \\&\qquad\qquad +\sqrt 2\bigg((\sqrt 6+\sqrt 2)^{N}-(\sqrt 6-\sqrt 2)^{N}\bigg) \\\\&=\sqrt 6\sum_{i=0}^{N}\binom Ni(\sqrt 6)^{N-i}\bigg((\sqrt 2)^i+(-\sqrt 2)^i\bigg) \\&\qquad\qquad +\sqrt 2\sum_{i=0}^{N}\binom Ni(\sqrt 6)^{N-i}\bigg((\sqrt 2)^i-(-\sqrt 2)^i\bigg) \\\\&=\sum_{j=0}^{(N-1)/2}\binom N{2j}6^{(N+1-2j)/2}\cdot 2^{j+1}+\sum_{j=1}^{(N+1)/2}\binom N{2j-1}6^{(N-2j+1)/2}\cdot 2^{1+j} \\\\&\equiv 6^{(N+1)/2}\cdot 2+2^{(N+3)/2}\pmod N \\\\&\equiv 12\cdot 2^{(N-1)/2}\cdot 3^{(N-1)/2}+4\cdot 2^{(N-1)/2}\pmod N \\\\&\equiv 12\cdot (-1)^{(N^2-1)/8}\cdot \frac{(-1)^{(N-1)/2}}{\bigg(\frac N3\bigg)}+4\cdot (-1)^{(N^2-1)/8}\pmod N \\\\&\equiv 12\cdot 1\cdot \frac{-1}{1}+4\cdot 1\pmod N \\\\&\equiv -8\pmod N\end{align}$$

So, we get $$2^{N+1}S_{n-2}^2-2^{N+2}\equiv -8\pmod N$$ It follows from $2^{N-1}\equiv 1\pmod N$ that $$S_{n-2}\equiv 0\pmod N$$

| cite | improve this answer | |

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.