Characterization of Chebyshev Numbers

David Pokrass Jacobs ; Mohamed O. Rayes ; Vilmar Trevisan

Algebra and discrete mathematics, no. 2 (2008), pp. 65-82.

Résumé

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.

Détail

Keywords: Chebyshev polynomials, polynomial factorization, resultant, Carmichael numbers.
Mots-clés : pseudoprimes