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}&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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.