Can you provide a proof or a counterexample for the following claim ?
Let $n$ be an odd 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 $P_n(x)$ be Legendre polynomial , then $n$ is a prime number if and only if $P_n(x) \equiv x^n \pmod {x^r-1,n}$ .
You can run this test here .
I have tested this claim up to $2 \cdot 10^4$ and there were no counterexamples .
On
This is a partial answer.
This answer proves that if $n$ is an odd prime number, then $P_n(x) \equiv x^n \pmod {x^r-1,n}$.
Proof :
Using the following expression $$P_n(x)=\frac{1}{2^n}\sum_{k=0}^{n}\binom{n}{k}^2(x-1)^{n-k}(x+1)^k$$
we have, by the binomial theorem, $$\begin{align}&2^n\left(P_n(x)-x^n\right) \\\\&=-2^nx^n+\sum_{k=0}^{n}\binom{n}{k}^2(x-1)^{n-k}(x+1)^k \\\\&=-2^nx^n+(x-1)^{n}+(x+1)^n+\sum_{k=1}^{n-1}\binom{n}{k}^2(x-1)^{n-k}(x+1)^k \\\\&=-2^nx^n+\sum_{k=0}^{n}\binom nkx^{n-k}((-1)^{k}+1)+\sum_{k=1}^{n-1}\binom{n}{k}^2(x-1)^{n-k}(x+1)^k \\\\&=-2^nx^n+2\sum_{j=0}^{(n-1)/2}\binom n{2j}x^{n-2j}+\sum_{k=1}^{n-1}\binom{n}{k}^2(x-1)^{n-k}(x+1)^k \\\\&=(-2^n+2)x^n+2\sum_{j=1}^{(n-1)/2}\binom n{2j}x^{n-2j}+\sum_{k=1}^{n-1}\binom{n}{k}^2(x-1)^{n-k}(x+1)^k \end{align}$$
Now, we have $-2^n+2\equiv 0\pmod n$ by Fermat's little theorem. Also, since $\binom nm\equiv 0\pmod n$ for $1\le m\le n-1$, we see that there is a polynomial $f$ with integer coefficients such that $$2^n\left(P_n(x)-x^n\right)=nf$$ from which $$P_n(x)=x^n+(x^r-1)\times 0+n\times \frac{1}{2^n}f$$ follows.
It follows from this and $\gcd(n,2^n)=1$ that $$P_n(x) \equiv x^n \pmod {x^r-1,n}\qquad\square$$
See here for more information. This covers the test you are describing, however it is stated as a conjecture, not a primality test.