11
$\begingroup$

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 .

$\endgroup$
6
  • $\begingroup$ For 1729 it gives prime albeit 1729 being composite. $\endgroup$
    – Cecilia
    Apr 10, 2018 at 8:26
  • $\begingroup$ @Richard Did you run pari/gp code provided by me ? $\endgroup$
    – Pedja
    Apr 10, 2018 at 8:50
  • $\begingroup$ I did, now I tested it again and it gave "composite" and the third time a syntax error. $\endgroup$
    – Cecilia
    Apr 10, 2018 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, 2018 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, 2018 at 19:44

1 Answer 1

2
+50
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .