Chebyshev polynomials of the first kind and primality testing Can you provide a proof or a counterexample for the claim given below ? 
Inspired by Agrawal's conjecture in this paper and by Theorem 4 in this paper I have formulated the following claim :

Let $n$ be a natural number greater than two . Let $r$ be the smallest odd prime number such that $r \nmid n$ and $n^2 \not\equiv 1 \pmod r$ . Let $T_n(x)$ be Chebyshev polynomial of the first kind , then $n$ is a prime number if and only if $T_n(x) \equiv x^n \pmod {x^r-1,n}$ .

You can run this test here .
I have tested this claim up to $5 \cdot 10^4$ and there were no counterexamples .
EDIT
Algorithm implementation in Sage without directly computing $T_n(x)$ .
Python script that implements this test can be found here.
The Android app that implements this test can be found on Google Play.
ADDED
I offer $100$ € for a proof of this claim. The proof must be published in one of the following journals: Journal of Number Theory , Algebra & Number Theory , Moscow Journal of Combinatorics and Number Theory .
 A: Decided to make a cw answer with an illustration of time growth.
I've tried on Mathematica this:
isprime[n_] := 
 With[{r = smallestr[n]}, 
  If[r == 0, n == 2, 
   PolynomialMod[PolynomialRemainder[ChebyshevT[n, t] - t^n, t^r - 1, t], n] === 0
  ]
 ]

where
smallestr[n_] := Module[{r},
  If[n==1 \[Or] EvenQ[n], Return[0]];
  For[r = 3, MemberQ[{0, 1, r - 1}, Mod[n, r]], r = NextPrime[r + 1],
   If[r < n \[And] Mod[n, r] == 0, Return[0]]
  ];
  r
 ]

I've run it on $n$ up to about 31000 (all answers are correct); here is the graph of time needed as a function of $n$.

Growth looks like faster than polynomial - the graph of $\log(\text{time}(n))/\log(n)$ does not seem to stabilize:

On the other hand a rough upper bound on growth can be deduced from the fact that $\log(\text{time}(n))/(n\log(n))$ seems to go down:

Some additional remarks.
(0)
Datapoints are only for those $n$ which have positive value of smallestr, i. e. such that the corresponding $r$ is smaller than any nontrivial divisor of $n$. Understandably, for other $n$ calculation is qualitatively quicker.
(1)
Finding $r$ is very efficient:
$$
\begin{array}{c|c}
r&\text{smallest $n$ that requires this $r$}\\
\hline
11&29\\
13&419\\
19&1429\\
23&315589\\
29&734161\\
31&1456729
\end{array}
$$
(2)
Seems like $n$ is prime iff all coefficients of $T_n(x)-x^n$ are divisible by $n$. If true, this must be well known of course, but I don't know. Should be provable from the explicit form of coefficients of $T_n$.
(2')
Given (2), it is obvious that at prime $n$ the algorithm gives correct answer. To also prove that it detects composite $n$ one has to show the following. Denote by $a_0$, ..., $a_n$ the coefficients of $T_n(x)-x^n$. Then, if some of the $a_i$ is not divisible by $n$, then also one of the sums $s_j:=a_j+a_{j+r}+a_{j+2r}+...$, $j=0,...,r-1$ is not divisible by $n$. Seemingly if $a_j$ is not divisible by $n$ then $j$ is not coprime to $n$; maybe this can help.
A: I do not share excitement about this test and believe it admits false positives (i.e., pseudoprimes). Here are some supporting arguments.
Assuming that $n\equiv 2\text{ or }3\pmod{5}$, we will have $r=5$. A square-free composite integer $n$ will pass the test for $r=5$ if $T_n(x)\equiv x^n\pmod{x^5-1,p}$ for every prime $p\mid n$. At the same time, it can be seen that
\begin{split}
T_n(x) \equiv x^n\pmod{x^5-1,\ 3}\quad&\Longleftrightarrow\quad n\equiv 3,\ 27,\ 38,\text{ or } 137\pmod{205}\\
T_n(x) \equiv x^n\pmod{x^5-1,\ 7}\quad&\Longleftrightarrow\quad n\equiv 7,\ 343,\ 858,\text{ or } 4797\pmod{6005}\\
T_n(x) \equiv x^n\pmod{x^5-1,\ 13}\quad&\Longleftrightarrow\quad n\equiv 13,\ 2197,\ 14268,\text{ or } 54927\pmod{71405}
\end{split}
and so on. In general, for a prime $p\equiv 2,3\pmod5$
$$T_n(x) \equiv x^n\pmod{x^5-1,\ p}\quad\Longleftrightarrow\quad n\equiv p,\ p^3,\ p^5,\text{ or } p^7\pmod{5q_p},$$
where $q_p$ is the period of $T_n(x)\pmod{x^5-1,\ p}$.
(Similar congruences hold for $r=7$.)
It is not clear why certain $n$ cannot satisfy such congruences modulo every $p\mid n$. I do not say that it is easy to find such $n$, but its existence seems quite plausible.
P.S. Also, notice that in the AKS test the value of $r$ is taken satisfying $r>\log(n)^2$ (in fact, even the order $o_r(n)>\log(n)^2$), and this makes huge difference. Perhaps, the present test can be saved from pseudoprimes as well by requiring $r$ be of the magnitude of $\log(n)$ or so.
UPDATE (2021-10-02). Congruences above have been corrected. Here is a Sage code for computing $q_p$.
A: Wow. This deserves a separate answer.
As I mentioned in a comment, motivated by the question, in a previous comment, by Igor Rivin whether an efficient primality test can be made if the statement in the question is true, I asked a separate question about whether one could efficiently compute $T_n(x)$ modulo $x^r-1,n$. That question got a brilliant answer by Lucia, which enables to really demonstrate that if the statement in the question is true, one indeed obtains a very efficient primality test based on it.
I made this quick-and-dirty Mathematica code
polmul[f_, g_, r_, n_] := Mod[f.NestList[RotateRight, g, r - 1], n]

matmul[a_, b_, r_, n_] :=  Mod[
 {{polmul[a[[1, 1]], b[[1, 1]], r, n] + polmul[a[[1, 2]], b[[2, 1]], r, n], 
   polmul[a[[1, 1]], b[[1, 2]], r, n] + polmul[a[[1, 2]], b[[2, 2]], r, n]}, 
  {polmul[a[[2, 1]], b[[1, 1]], r, n] + polmul[a[[2, 2]], b[[2, 1]], r, n], 
   polmul[a[[2, 1]], b[[1, 2]], r, n] + polmul[a[[2, 2]], b[[2, 2]], r, n]}}, n]

matsq[a_, r_, n_] := matmul[a, a, r, n]

matpow[a_, k_, r_, n_] := If[k == 1, a,
 If[EvenQ[k],
  matpow[matsq[a, r, n], k/2, r, n], 
  matmul[a, matpow[matsq[a, r, n], (k - 1)/2, r, n], r, n]
 ]
]

xmat[r_, n_] :=
 {{PadRight[{0, 2}, r], PadRight[{n - 1}, r]},
  {PadRight[{1}, r], ConstantArray[0, r]}}

isprime[n_] := With[{r = smallestr[n]}, 
 If[r == 0, n == 2,
  With[{xp = matpow[xmat[r, n], n - 1, r, n]},
   Mod[RotateRight[xp[[1, 1]]] + xp[[1, 2]], n]
    === PadRight[Append[ConstantArray[0, Mod[n, r]], 1], r]
  ]
 ]
]

where smallestr is as in my other answer.
Running this on $n$ up to 100000 (all answers correct) gives the following timing:

Seems that it is of at worst logarithmic order (as that answer by Lucia suggests) - actually the graph of $\log(\operatorname{time}(n))/\log\log(n)$ looks almost like going to be bounded above:

Since the algorithm involves a recursive procedure for matrix powers, in principle one also has to check memory use. Here I must confess results are strange, maybe it is something hardware-specific.
$$
\begin{array}{r|l}
\text{amount of memory}&\text{number of cases (out of 100000)}\\
\hline
32&1407\\
64&94408\\
80&1\\
288&1\\
320&42\\
352&3\\
392&8\\
424&2316\\
456&1812\\
3452552&1
\end{array}
$$
This last amount 3452552 corresponds to $n=65969$, I have no idea why it needed so much memory. As I said this might be something machine specific - maybe some garbage collection occurred at that point or something like that. Anyway, as opposed to memory measurement timing data seem to be very accurate, I used the Mathematica command AbsoluteTiming and documentation says it gives actual processor time used for the calculation with quite high precision.
