Can you provide a proof or a counterexample for the claim given below?
Inspired by Lucas-Lehmer test I have formulated the following claim :
Let $T_n(x)$ be the nth Chebyshev polynomial of the first kind. Let $M_p=2^p-1$ such that $p$ is an odd prime. Let $S_i=T_4(S_{i-1})$ with $S_0=2$ . Then , $M_p$ is prime iff $S_{(p-1)/2} \equiv -1 \pmod{M_p}$
You can run this test here .
I have verified this claim for all $p$ up to $10000$ .
Best Answer
Your test is in fact equivalent to the Lucas Lehmer test. First of all because of $$f(f(x))=T_4(x)$$ with $$f(x)=2x^2-1$$ your test is equivalent to the following test :
If $$S_0=2$$ and $$S_{i+1}=f(S_i)$$ then $$2^p-1$$ is prime if and only if $$S_{p-1}\equiv -1\mod M_p$$
If we compare to Lucas-Lehmer, we have $$T_0=4$$ $$T_{i+1}=T_i^2-2$$ then the statement is that $$2^p-1$$ is prime if and only if $$T_{p-2} \equiv 0\mod M_p$$ which is equivalent to $$T_{p-1}\equiv -2\mod M_p$$
We can easily show $T_i=2S_i$ for all $i$ by considering $$x^2-2=2(2(\frac{x}{2})^2-1)$$ and from this the equivalence easily follows.