<s>[INST] Primality test using Chebyshev and Legendre polynomials 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 ?
 [/INST] 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$.
</s>