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 .


Mathematica implementation of test :

While[Mod[n,r]==0 || PowerMod[n,2,r]==1,r=NextPrime[r]];
  • $\begingroup$ what does "mod $x^r-1,n$" mean ? $\endgroup$
    – Peter
    Sep 5, 2018 at 12:55
  • $\begingroup$ @Peter See step 5 : en.wikipedia.org/wiki/… $\endgroup$
    – Peđa
    Sep 5, 2018 at 13:49

1 Answer 1


This is a partial answer.

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.


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.