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 .

  • $\begingroup$ For 1729 it gives prime albeit 1729 being composite. $\endgroup$ – Richard Apr 10 '18 at 8:26
  • $\begingroup$ @Richard Did you run pari/gp code provided by me ? $\endgroup$ – Peđa Terzić Apr 10 '18 at 8:50
  • $\begingroup$ I did, now I tested it again and it gave "composite" and the third time a syntax error. $\endgroup$ – Richard Apr 10 '18 at 10:18
  • $\begingroup$ I wonder what $\displaystyle\sum_{k=0}^{n-1}F_{n}(k) \bmod n$ is in general. $\endgroup$ – lhf Apr 10 '18 at 12:41
  • $\begingroup$ 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) $\endgroup$ – Sil Apr 10 '18 at 19:44

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.

| cite | improve this answer | |

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.