# A congruence involving Fibonacci polynomials

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

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

You can run this test here .

• For 1729 it gives prime albeit 1729 being composite. – Richard Apr 10 '18 at 8:26
• @Richard Did you run pari/gp code provided by me ? – Peđa Terzić Apr 10 '18 at 8:50
• I did, now I tested it again and it gave "composite" and the third time a syntax error. – Richard Apr 10 '18 at 10:18
• I wonder what $\displaystyle\sum_{k=0}^{n-1}F_{n}(k) \bmod n$ is in general. – lhf Apr 10 '18 at 12:41
• Maybe the fact that $F_n(x)=\sum_{i=0}^{\lfloor n/2\rfloor}\binom{n-1-i}{i}x^{n-2i-1}$ could be used, somehow... (some exchange of summation order and stuff perhaps) – Sil Apr 10 '18 at 19:44

## 1 Answer

One direction, proving $\sum_{k} F_p(k)\equiv -1\pmod{p}$ when $p$ is prime, is easy.

Let $\sigma_i=\sum_{k=0}^{p-1}k^i$, and let $f_{i}$ be the coefficient of $x^i$ in $F_p(x)$. Then $\sum_{k} F_p(k)\equiv \sum_i f_{i}\sigma_i$. You can show that $\sigma_i\equiv0$ for all $i=0,1,\dots,p-2$, while $\sigma_{p-1}\equiv-1$. Since the $x^{p-1}$ coefficient of $F_{p}(x)$ is $1$, the result follows.