2
$\begingroup$

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.

EDIT

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

$\endgroup$
2
  • 1
    $\begingroup$ I think you should refer this question to that your new one. $\endgroup$ May 27, 2020 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, 2020 at 10:45

1 Answer 1

3
+50
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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