# 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 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.