Primality test using Chebyshev polynomials of the first kind

Question

Can you provide a proof or a counterexample for the claim given below ?

Inspired by the Lucas primality test I have formulated the following claim :

Let $n$ be a natural number greater than two and $n \neq 5$ . Let $T_n(x)$ be Chebyshev polynomial of the first kind . If there exists an integer $a$ , $1<a<n$ , such that $T_{n-1}(a) \equiv 1 \pmod n$ and for every prime factor $q$ of $n-1$ , $T_{(n-1)/q}(a) \not\equiv 1 \pmod n$ then $n$ is prime . If no such number $a$ exists then $n$ is composite .

Implementation of test in 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["prime"]; Break[]]]];
If[k == 0, Print["composite"]];

I have tested this claim up to $n=5000$ .

Answer 1

I use a slightly different definition here:

The iterations follow T(n+1) = a T(n) - a T(n-1), where the first kind start at S(0)=0, S(1)=1, and the second kind starts at C(0)=2, C(1)=a.

The statement is true for what is proposed, but it's equally true when you use p+1. The proof of this is to use the double of the second kind, which amounts to the likes of $A^n + A^{-n}$.

Relative to modulo p, this divides into two series, one corresponding to C(p-1)=2, the other to C(p+1)=2. From this, if either of these conditions both, then p is composite.

The proof for C(p-1)=2 relies on being able to extract some value where $q^{(p-1)}$ = 1, mod p. Then we get a = q+(1/q) from using the cyclotomic series. But it can be shown that this series only uses half the available modulii for p.

If one calculates the gaussian residue of $(a^2 - 2)$ against p, then it divides p-1 if the residue is +1, and p+1 if the residue is -1. A proof for this exists, but is lost, but it has been demonstrated for p to 200,000,000 for some values of a.