3
$\begingroup$

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)))
}
$\endgroup$
2
+50
$\begingroup$

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$$

| cite | improve this answer | |
$\endgroup$

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.