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 :


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 ?

  • $\begingroup$ 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)." $\endgroup$
    – user25406
    Jul 28, 2017 at 19:23
  • 1
    $\begingroup$ @user25406 We have 2 min CPU time limit per computation . The number 5394826801 is too big . $\endgroup$
    – Peđa
    Jul 29, 2017 at 1:24
  • $\begingroup$ can you please explain the motivation of adding the Legendre polynomial condition to get a primality test? thanks. $\endgroup$
    – user25406
    Jul 29, 2017 at 14:11
  • 1
    $\begingroup$ @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 . $\endgroup$
    – Peđa
    Jul 29, 2017 at 14:41

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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