# 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 ?

• I tried sage cell on 5394826801 and got an error message. I was trying to find out if it can deal with Carmichael numbers. I got this error mesg "PARI/GP interpreter crashed -- automatically restarting. *** at top-level: if((Mod(polchebyshev(n,1,3),n)==3),if((Mo *** ^-------------------- *** incorrect type in gtos [integer expected] (t_POL)." Jul 28, 2017 at 19:23
• @user25406 We have 2 min CPU time limit per computation . The number 5394826801 is too big .
– Peđa
Jul 29, 2017 at 1:24
• can you please explain the motivation of adding the Legendre polynomial condition to get a primality test? thanks. Jul 29, 2017 at 14:11
• @user25406 The main idea behind this test is essentially similar to the idea behind Baillie-PSW primality test . I made the assumption that list of Chebyshev pseudoprimes base 3 and a list of Legendre pseudoprimes base 3 have no overlap .
– Peđa
Jul 29, 2017 at 14:41

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