Primalidade e polinômios de Chebyshev

Abstract

Este trabalho faz uma relação entre primalidade de números inteiros e os polinômios de Chebyshev, estudando resultados recentemente descobertos. Um dos principais resultados é uma generalização do Pequeno Teorema de Fermat, que mostra a congruência, Tn(a) =a ( mod n) para n primo, em que Tn(x) é o n- ésimo polinômio de Chebyshev. A recíproca desse resultado, se verdadeira, conduziria a um teste de primalidade determinístico eficiente. Através de cálculo computacional, mostramos que para n < 1,9 x 104 , a recíproca é verdadeira. Além disso, os resultados dessa simulação, podem servir de base para o desenvolvimento de um algoritmo probabilístico para verificação da primalidade. Alguns testes de primalidade existentes na literatura, assim como definições e propriedades algébricas dos polinômios de Chebyshev também são apresentadas.

This work makes a relation between integer primality and Chebyshev polynomials, discussing recently found results. One of the most important results is a generalization of Fermat's little theorem. lt shows that Tn(a) =a ( mod n ), for n prime, where Tn(x) is the ndegree Chebyshev polynomial. The converse o f this result, if true, would lead to an efficient deterministic primality test. Tbrough a machine computation, we show that for n < 1,9 x 1 04 , the converse is true. The results of this simulation may serve to structure a probabilistic primality testing algorithm. Also, some existent primality tests, as well as definitions and algebraic properties o f Chebyshev polynomials are presented.