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

Inspired by Agrawal's conjecture in [this paper][1] and by Theorem 4 in [this paper][2] 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][3] .

I have tested this claim up to $5 \cdot 10^4$ and there were no counterexamples .

**EDIT**

[Algorithm implementation in Sage][4] without directly computing $T_n(x)$ .

Python script that implements this test can be found [here][5].

The Android app that implements this test can be found on [Google Play][6].

**ADDED**

I offer $100$ € for a proof of this claim. Proof must be published in [Journal of Number Theory][7]. 


  [1]: https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
  [2]: http://icm.mcs.kent.edu/reports/1999/chebpol.pdf
  [3]: https://sagecell.sagemath.org/?z=eJw9jU0KgzAQhfeF3iEIhRkaoalLyRF6BRe1kQTiJIyhjeDhHYS6Gd58vB-ynemvF7ad3J8P0cErfYA0o7UPtW0qhqmcbHgKNkqzJVdL5jA74LtBlHSYDhvkFEfv3uvi3VdCRlfEG9SBW4OasAXRdBJUsqOliQo0R2GD_3dMc05LKIKw3wGYCjLD&lang=gp
  [4]: https://sagecell.sagemath.org/?z=eJxtUcFO4zAQvfMVQyWIXRmUBK2QCJZW4gzisLcorZzUaSOScWQ7SxDsfvuOk1C6Er7Y43kz782bfX-tf6uWrcZOeWYFcpCQp-tRwFWSQSIgLtaPZscSMW7sVcKXAHm24mf7z2rXqbbVzluGXL43NUMpE_j4ALxIpYwFWO0HiyzmPKuN7W3TaWaJ6kaAMaJ7Y4PEC8uzpgZ6yhguL8HCPeB_pVP2fM7SnSw36TrCLCfcn1Nt3VvjZsKgjagC76nguS_9SvhSiiFMKUcFY08VR4M2uM5HkRR_eTb2eVoEYDBlPFqzWLXBSchO1_Bw0NULUd2dAR2iw_t0foczUwJbPQ1dqS10g_NQathbrTzF_qAQDOpz6hbwuqUONF89YOUbg9uKhjkZdCVyLPi1U3vNuJTeDvobsucA_WrpvsM8mK43rvET7meDpEZVfhppSztusB_8tjQjS-PkVkSz_rtIvDY7f5DJzQ8u1CRROt3qyhvL8mgyIypEOXhv0MlfpE-0qtStjCK-eDSXke_TEueIw5RyB_MKy1dY3z94C9NF&lang=sage&interacts=eJyLjgUAARUAuQ==
  [5]: https://gist.github.com/PedjaTerzic/9caad402e11a5687962b9a7d9e1ed238
  [6]: https://play.google.com/store/apps/details?id=chebyshev.com.calculater&hl=en
  [7]: https://www.journals.elsevier.com/journal-of-number-theory