Legendre polynomials and primality testing 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 .
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}&amp;2^n\left(P_n(x)-x^n\right)
\\\\&amp;=-2^nx^n+\sum_{k=0}^{n}\binom{n}{k}^2(x-1)^{n-k}(x+1)^k
\\\\&amp;=-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
\\\\&amp;=-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
\\\\&amp;=-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
\\\\&amp;=(-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.