Characterization of Chebyshev Numbers

Abstract

Let \(T_n(x)\) be the degree-\(n\) Chebyshev polynomial of the first kind. It is known [1,13] that \(T_p(x) \equiv x^p \bmod{p}\), when \(p\) is an odd prime, and therefore, \(T_p(a) \equiv a \bmod{p}\) for all \(a\). Our main result is the characterization of composite numbers \(n\) satisfying the condition \(T_n(a) \equiv a \bmod{n}\), for any integer \(a\). We call these pseudoprimes  Chebyshev numbers, and show that \(n\) is a Chebyshev number if and only if \(n\) is odd, squarefree, and for each of its prime divisors \(p\), \(n \equiv \pm 1 \bmod p-1\) and \(n \equiv \pm 1 \bmod p+1\). Like Carmichael numbers, they must be the product of at least three primes. Our computations show there is one Chebyshev number less than \(10^{10}\), although it is reasonable to expect there are infinitely many. Our proofs are based on factorization and resultant properties of Chebyshev polynomials.