# 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"]];

• what does "mod $x^r-1,n$" mean ? Sep 5, 2018 at 12:55
• @Peter See step 5 : en.wikipedia.org/wiki/…
– Peđa
Sep 5, 2018 at 13:49

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.