Can you provide a proof or a counterexample for the claim given below ?
Inspired by Agrawal's conjecture in this paper I have formulated the following claim :
Let $n$ be a natural number greater than one . Let $r$ be the smallest odd prime number such that $r \nmid n$ and $n^2 \not\equiv 1 \pmod r$ . Let $L_n(x)$ be Lucas polynomial , then $n$ is a prime number if and only if $L_n(x) \equiv x^n \pmod {x^r-1,n}$ .
You can run this test here or here .
I have tested this claim up to $2 \cdot 10^4$ and there were no counterexamples .
EDIT
Mathematica implementation of test :
n=31;
r=3;
While[Mod[n,r]==0 || PowerMod[n,2,r]==1,r=NextPrime[r]];
If[PolynomialMod[PolynomialRemainder[LucasL[n,x],x^r-1,x],n]-PolynomialRemainder[x^n,x^r-1,x]===0,Print["prime"],Print["composite"]];