Lucas polynomials and primality testing 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"]];

 A: This is a partial answer.
This answer proves that if $n$ is a prime number, then $L_n(x) \equiv x^n \pmod {x^r-1,n}$.

Lemma : For every positive integer $n$, there are integers $a_0,a_1,\cdots, a_{n-1}$ such that
$$L_n(x)=x^n+\sum_{k=0}^{n-1}a_kx^k$$
Proof for lemma :
The claim is true for $n=1$ and $n=2$ : 
$$L_1(x)=x^1+0\cdot x^0,\quad L_2(x)=x^2+0\cdot x^1+2\cdot x^0$$
Supposing that the claim is true for $n-2,n-1$ gives
$$\begin{align}L_n(x)&=xL_{n-1}(x)+L_{n-2}(x)
\\\\&=x\left(x^{n-1}+\sum_{k=0}^{n-2}a_kx^k\right)+x^{n-2}+\sum_{k=0}^{n-3}b_kx^k
\\\\&=x^n+\sum_{k=0}^{n-2}a_kx^{k+1}+x^{n-2}+\sum_{k=0}^{n-3}b_kx^k
\\\\&=x^n+a_{n-2}x^{n-1}+(a_{n-3}+1)x^{n-2}+\sum_{k=1}^{n-3}(a_{k-1}+b_k)x^k+b_0\end{align}$$
where $a_0,a_1,\cdots,a_{n-2},b_0,b_1,\cdots,b_{n-3}$ are integers.
So, the claim is true for $n$. $\quad\square$
For $n=2$, we get
$$L_2(x)=x^2+(x^r-1)\times 0+2\times 1\equiv x^2\pmod{x^r-1,2}$$
In the following, $n$ is an odd prime.
By the binomial theorem,$$\begin{align}2^nL_n(x)&=\left(x-\sqrt{x^2+4}\right)^n+\left(x+\sqrt{x^2+4}\right)^n
\\\\&=\sum_{k=0}^{n}\binom nkx^{n-k}\left(-\sqrt{x^2+4}\right)^k+\sum_{k=0}^{n}\binom nkx^{n-k}\left(\sqrt{x^2+4}\right)^k
\\\\&=\sum_{k=0}^{n}\binom nkx^{n-k}\left(\left(-\sqrt{x^2+4}\right)^k+\left(\sqrt{x^2+4}\right)^k\right)
\\\\&=\sum_{j=0}^{(n-1)/2}\binom n{2j}x^{n-2j}\cdot 2\left(\sqrt{x^2+4}\right)^{2j}
\\\\&=\sum_{j=0}^{(n-1)/2}\binom n{2j}x^{n-2j}\cdot 2(x^2+4)^{j}
\\\\&=\sum_{j=0}^{(n-1)/2}\binom n{2j}x^{n-2j}\cdot 2\sum_{k=0}^{j}\binom jk(x^2)^{j-k}\cdot 4^{k}
\\\\&=\sum_{j=0}^{(n-1)/2}\sum_{k=0}^{j}x^{n-2k}\cdot 2^{2k+1}\binom n{2j}\binom jk
\\\\&=2x^{n}+\sum_{j=1}^{(n-1)/2}\sum_{k=0}^{j}x^{n-2k}\cdot 2^{2k+1}\binom n{2j}\binom jk
\\\\&=2x^{n}+\sum_{j=1}^{(n-1)/2}\left(x^{n}\cdot 2\binom n{2j}+\sum_{k=1}^{j}x^{n-2k}\cdot 2^{2k+1}\binom n{2j}\binom jk\right)
\\\\&=2x^{n}+\sum_{j=1}^{(n-1)/2}x^{n}\cdot 2\binom n{2j}+\sum_{j=1}^{(n-1)/2}\sum_{k=1}^{j}x^{n-2k}\cdot 2^{2k+1}\binom n{2j}\binom jk
\\\\&=2x^n\sum_{j=0}^{(n-1)/2}\binom n{2j}+\sum_{j=1}^{(n-1)/2}\sum_{k=1}^{j}x^{n-2k}\cdot 2^{2k+1}\binom n{2j}\binom jk
\\\\&=2x^n\cdot 2^{n-1}+\sum_{j=1}^{(n-1)/2}\binom n{2j}\sum_{k=1}^{j}x^{n-2k}\cdot 2^{2k+1}\binom jk
\end{align}$$
from which
$$L_n(x)=x^n+\frac{1}{2^n}\sum_{j=1}^{(n-1)/2}\binom n{2j}\sum_{k=1}^{j}x^{n-2k}\cdot 2^{2k+1}\binom jk$$
follows.
From the lemma and the fact that $\binom nm\equiv 0\pmod n$ for $1\le m\le n-1$, there is a polynomial $f$ with integer coefficients such that
$$L_n(x)=x^n+(x^r-1)\times 0+nf$$
from which
$$L_n(x)\equiv x^n\pmod{x^r-1,n}$$
follows.
