Primality test using Chebyshev and Legendre polynomials

Question

Inspired by Theorem 5 in this paper I have formulated the following claim :

Let $n$ be an odd number and $n>1$ . Let $T_n(x)$ be Chebyshev polynomial of the first kind and let $P_n(x)$ be Legendre polynomial , then $n$ is a prime number if and only if the following congruences hold simultaneously

$\bullet \: T_n(3) \equiv 3 \pmod n$

$\bullet \: P_n(3) \equiv 3 \pmod n$

You can run this test here .

I was searching for pseudoprimes using the following PARI/GP program :

CL(lb,ub)=
{
forstep(n=lb,ub,[2],
if(!ispseudoprime(n), 
if((Mod(polchebyshev(n,1,3),n)==3), 
if((Mod(pollegendre(n,3),n)==3),print(n)))))
}

I have tested this claim up to $1.4 \cdot 10^6$ and there were no counterexamples .

Question : Can you provide a proof or a counterexample for the claim given above ?

Answer 1

This is a partial answer.

This answer proves that if $n$ is an odd prime, then $P_n(3)\equiv 3\pmod n$.

Using that $\binom nk\equiv 0\pmod n$ for $1\le k\le n-1$, we have $$\begin{align}P_n(3)&=\frac{1}{2^n}\sum_{k=0}^{n}\binom nk^2(3-1)^{n-k}(3+1)^k\\\\&=\frac{1}{2^n}\sum_{k=0}^{n}\binom nk^2\cdot 2^{n-k}\cdot 2^{2k}\\\\&=\sum_{k=0}^{n}\binom nk^2\cdot 2^k\\\\&\equiv \binom n0^2\cdot 2^0+\binom nn^2\cdot 2^n\quad\pmod n\\\\&\equiv 1+2^n\quad\pmod n\end{align}$$

Now, since $\frac{n^2-1}{4}$ is even when $n$ is odd, we have $$\begin{align}P_n(3)&\equiv 1+2^n\equiv 1+2\cdot\left(2^{\frac{n-1}{2}}\right)^2\equiv 1+2\cdot \left((-1)^{\frac{n^2-1}{8}}\right)^2\equiv 1+2\cdot (-1)^{\frac{n^2-1}{4}}\\\\&\equiv 3\pmod n\qquad\blacksquare\end{align}$$

---

According to Theorem 5 in the paper you showed, we can say that if $n$ is an odd prime, then $T_n(3)\equiv 3\pmod n$.

Therefore, we can say that if $n$ is an odd prime, then $T_n(3)\equiv P_n(3)\equiv 3\pmod n$.