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 PARI/GP][4] without directly computing $T_n(x)$ .

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

An Android app that implements this test can be found [here][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=eJxVUNtqwzAMfc9XaIUWO7gQpw9leP6EfkFIoGwJGGo5KC64tNu3T25C1j1JR5ejo4NWvx8Ppkj-HAUplGChqcukYK8NaAVVW57Cl9AqdbTXcgEoTTH58-XST5EESnt3g0BrNTwegNva2koB9fFKKCopzRBoJOd7Qcx_UBCC8jdxtbgladwAnNoKdjsg-AD8t_rsvs1djnqJLGYdI8lz34W_uWm-kgUxfz72qnIm46qFP3mYYc09Xkgjb6xWdFg2Sen2R5o0NnWbB_P7aTVhMaVDvs4GvApQnGAUmyferPAz-DFMLnJJml9w3HEY&lang=gp&interacts=eJyLjgUAARUAuQ==
  [5]: https://gist.github.com/PedjaTerzic/9caad402e11a5687962b9a7d9e1ed238
  [6]: https://www.amazon.com/gp/product/B081V2CMDS
  [7]: https://www.journals.elsevier.com/journal-of-number-theory