Prueba de primalidad utilizando polinomios de Chebyshev de primer tipo

Question

¿Puedes proporcionar una prueba o un contraejemplo para la afirmación dada a continuación?

Inspirado por el test de primalidad de Lucas he formulado la siguiente afirmación:

Sea $n$ un número natural mayor que dos y $n \neq 5$. Sea $T_n(x)$ el polinomio de Chebyshev de primer tipo. Si existe un entero $a$, $1

Implementación de la prueba en Mathematica:

n = 31;
F = {};
f = 2;
While[f < n,
  If[Mod[n - 1, f] == 0, AppendTo[F, f]];
  f = NextPrime[f]];
k = 0;
For[a = 2, a < n, a++,
  If[PolynomialMod[ChebyshevT[n - 1, a], n] == 1,
   j = 0;
   For[i = 1, i <= Length[F], i++,
    If[!(PolynomialMod[ChebyshevT[(n - 1)/F[[i]], a], n] == 1), j++, 
     Break[]]];
   If[j == Length[F], k++; Print["primo"]; Break[]]]];
If[k == 0, Print["compuesto"]];

He probado esta afirmación hasta $n=5000$.

Answer 1

Utilizo una definición ligeramente diferente aquí:

Las iteraciones siguen T(n+1) = a T(n) - a T(n-1), donde el primer tipo comienza en S(0)=0, S(1)=1, y el segundo tipo comienza en C(0)=2, C(1)=a.

La afirmación es verdadera para lo que se propone, pero también es verdadera cuando se usa p+1. La demostración de esto es utilizar el doble del segundo tipo, lo cual equivale a algo como $A^n + A^{-n}$.

En relación al módulo p, esto se divide en dos series, una correspondiente a C(p-1)=2, y la otra a C(p+1)=2. A partir de esto, si cualquiera de estas condiciones se cumple, entonces p es compuesto.

La demostración de C(p-1)=2 se basa en poder extraer algún valor donde $q^{(p-1)}$ = 1, mod p. Luego obtenemos a = q+(1/q) usando la serie cíclica. Pero se puede mostrar que esta serie solo utiliza la mitad de los módulos disponibles para p.

Si uno calcula el residuo gaussiano de $(a^2 - 2)$ respecto a p, entonces divide p-1 si el residuo es +1, y p+1 si el residuo es -1. Existe una demostración para esto, pero se ha perdido, aunque se ha demostrado para p hasta 200,000,000 para algunos valores de a.