A congruence involving Lucas polynomials

Question

Can you provide a proof or a counterexample to the following claim :

Let $n$ be a natural number greater than two and let $L_{n}(x)$ be Lucas polynomial , then $n$ is prime if and only if :$\displaystyle\sum_{k=0}^{n-1}L_{n-1}(k) \equiv -1 \pmod n$ .

You can run this test here .

I was searching for counterexample using the following two Pari/GP codes :

Lucas1(lb,ub)={
my(lucas(m,x)=
p0=2;
p1=x;
l=2;
while(l<=m,
p=x*p1+p0;
p0=p1;
p1=p;
l++);
return(p));
forprime(n=lb,ub,
if(!(Mod(sum(k=0,n-1,lucas(n-1,k)),n)==n-1),print(n)))
}


Lucas2(lb,ub)={
my(lucas(m,x)=
p0=2;
p1=x;
l=2;
while(l<=m,
p=x*p1+p0;
p0=p1;
p1=p;
l++);
return(p));
forcomposite(n=lb,ub,
if((Mod(sum(k=0,n-1,lucas(n-1,k)),n)==n-1),print(n)))
}

Answer 1

This is a partial answer.

This answer proves that if $n$ is an odd prime, then $$\sum_{k=0}^{n-1}L_{n-1}(k) \equiv -1 \pmod n\tag1$$

If $n=3$, then $(1)$ holds since $$\sum_{k=0}^{2}L_{2}(k)=L_2(0)+L_2(1)+L_2(2)=2+3+6\equiv -1\pmod 3$$

In the following, $n$ is prime greater than three.

Using $\left(k-\sqrt{k^2+4}\right)\left(k+\sqrt{k^2+4}\right)=-4$, we have $$\small\begin{align}-2\cdot 2^{n-1}L_{n-1}(k)&=\frac{-4}{2}\left(\left(k-\sqrt{k^2+4}\right)^{n-1}+\left(k+\sqrt{k^2+4}\right)^{n-1}\right)\\\\&=\frac{\left(k-\sqrt{k^2+4}\right)\left(k+\sqrt{k^2+4}\right)}{2}\left(\left(k-\sqrt{k^2+4}\right)^{n-1}+\left(k+\sqrt{k^2+4}\right)^{n-1}\right)\\\\&=\frac 12\left(k+\sqrt{k^2+4}\right)\left(k-\sqrt{k^2+4}\right)^{n}+\frac 12\left(k-\sqrt{k^2+4}\right)\left(k+\sqrt{k^2+4}\right)^{n}\\\\&=\frac k2\left(\left(k-\sqrt{k^2+4}\right)^{n}+\left(k+\sqrt{k^2+4}\right)^{n}\right)\\\\&\qquad\quad+\frac{\sqrt{k^2+4}}{2}\ \left(\left(k-\sqrt{k^2+4}\right)^{n}-\left(k+\sqrt{k^2+4}\right)^{n}\right)\end{align}$$

By the binomial theorem, $$\begin{align}-2\cdot 2^{n-1}L_{n-1}(k)&=\frac k2\sum_{i=0}^{n}\binom nik^{n-i}\left(\left(-\sqrt{k^2+4}\right)^i+\left(\sqrt{k^2+4}\right)^i\right)\\\\&\qquad \quad +\frac{\sqrt{k^2+4}}{2}\ \sum_{i=0}^{n}\binom nik^{n-i}\left(\left(-\sqrt{k^2+4}\right)^i-\left(\sqrt{k^2+4}\right)^i\right)\\\\&=\frac k2\sum_{j=0}^{(n-1)/2}\binom{n}{2j}k^{n-2j}\cdot 2\left(\sqrt{k^2+4}\right)^{2j}\\\\&\qquad\quad +\frac{\sqrt{k^2+4}}{2}\ \sum_{j=1}^{(n+1)/2}\binom{n}{2j-1}k^{n-(2j-1)}\cdot (-2)\left(\sqrt{k^2+4}\right)^{2j-1}\\\\&=\sum_{j=0}^{(n-1)/2}\binom{n}{2j}k^{n-2j+1}\left(k^2+4\right)^{j}-\sum_{j=1}^{(n+1)/2}\binom{n}{2j-1}k^{n-(2j-1)}\left(k^2+4\right)^{j}\end{align}$$

Since $k^{n-1}\equiv 1\pmod n$ for $1\le k\le n-1$, and $\binom nj\equiv 0\pmod n$ for $1\le j\le n-1$, we have $$2L_{n-1}(k)\equiv -k^{n+1}+(k^2+4)^{(n+1)/2}\equiv -k^2+(k^2+4)^{(n+1)/2}\pmod n$$

Therefore, letting $N:=\frac{n+1}{2}$, we have $$\begin{align}\sum_{k=0}^{n-1}2L_{n-1}(k)&\equiv -\sum_{k=0}^{n-1}k^2+\sum_{k=0}^{n-1}(k^2+4)^{N}\equiv -\frac{(n-1)n(2n-1)}{6}+\sum_{k=0}^{n-1}(k^2+4)^{N}\pmod n\\\\&\stackrel{*}\equiv \sum_{k=0}^{n-1}(k^2+4)^{N}\equiv 4^{N}+\sum_{k=1}^{n-1}\sum_{j=0}^{N}\binom Nj(k^2)^{j}\cdot 4^{N-j}\pmod n\\\\&\equiv 4+\sum_{j=0}^{N}\binom Nj\cdot 4^{N-j}S_{2j}\pmod n\tag2\end{align}$$ where $\stackrel{*}\equiv $ comes from that $(n-1)(2n-1)\equiv 0\pmod 6$, and we defined $S_i$ as $\displaystyle\sum_{k=1}^{n-1}k^i$.

Now, we use the following lemma :

Lemma : $S_0\equiv S_{n-1}\equiv -1\pmod n, S_{n+1}\equiv 0\pmod n$ and $S_i\equiv 0\pmod n$ for $1\le i\le n-2$.

Proof for the lemma :

We have $S_0\equiv \displaystyle\sum_{k=1}^{n-1}1\equiv -1\pmod n$. By Fermat's little theorem, $S_{n-1}\equiv S_0\equiv -1\pmod n$.

Next, let us prove $S_i\equiv 0\pmod n$ for $1\le i\le n-2$ by induction.

The base case : $S_1\equiv \displaystyle\sum_{k=1}^{n-1}k^1\equiv \frac{(n-1)n}{2}\equiv 0\pmod n$.

Suppose that $S_i\equiv 0\pmod n$ for $1\le i\le j$. Since we have $$2^{j+2}-1^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}1^i$$ $$3^{j+2}-2^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}2^i$$ $$\vdots$$ $$n^{j+2}-(n-1)^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}(n-1)^i$$ adding these, we get $$n^{j+2}-1=\sum_{k=1}^{n-1}\sum_{i=0}^{j+1}\binom{j+2}{i}k^i=\sum_{i=0}^{j+1}\binom{j+2}{i}S_i=n-1+(j+2)S_{j+1}+\sum_{i=1}^{j}\binom{j+2}{i}S_i$$ from which we have $$S_{j+1}=\frac{1}{j+2}\left(n^{j+2}-n-\sum_{i=1}^{j}\binom{j+2}{i}S_i\right)$$ By the inductive hypothesis, we see that $S_{j+1}\equiv 0\pmod n$ if $j\le n-3$.

Finally, by Fermat's little theorem, $S_{n+1}\equiv \displaystyle\sum_{k=1}^{n-1}k^{n+1}\equiv \displaystyle\sum_{k=1}^{n-1}k^{2}\equiv S_2\equiv 0\pmod n.\qquad\blacksquare$

Using the lemma, we have, from $(2)$,

$$\begin{align}\sum_{k=0}^{n-1}2L_{n-1}(k)&\equiv 4+\sum_{j=0}^{N}\binom Nj\cdot 4^{N-j}S_{2j}\pmod n\\\\&\equiv 4+\binom N0\cdot 4^{N-0}S_{0}+\binom N{(n-1)/2}\cdot 4^{N-(n-1)/2}S_{n-1}\pmod n\\\\&\equiv -2\pmod n\end{align}$$ It follows from $\gcd(n,2)=1$ that $$\sum_{k=0}^{n-1}L_{n-1}(k)\equiv -1\pmod n$$