3
$\begingroup$

Let $F(n)$ be $n$-th Fibonacci number.$F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3 \text{ and so on. }$Given a positive integer $n \gt 2$,Find the smallest prime number $P$ such that $P$ divides $F(n)$ but it does not divide any $F(k)$ smaller than $F(n)$ ?

Now,my question: Is it possible to find the answer without actually computing the value of $F(n)$?

I am looking for an interesting algorithm for this purpose.

  • 2
    @Lowther Indeed m=6 and m=12 are the only exception, the result however is true for all other m>2, a proof can be found here www.fq.math.ca/Scanned/39-5/boase.pdf2010-12-18

1 Answers 1

7

According to this article Factorisation of Fibonacci Numbers, if $F_n$ is the entry point in the Fibonacci sequence of the prime $p$ (i.e. $F_n$ is the smallest Fibonacci number divisible by the prime $p$) then for $p>5$ we have: for odd $n$

$p=4kn+1 \quad \textrm{ or } \quad p=(4k+2)n-1,$

for $n \equiv 2 \pmod{4}$

$p=kn+1,$

and for $n \equiv 0 \pmod{4}$

$p=2kn+1 \quad \textrm{ or } \quad p=(2k+1)n-1 .$

This should significantly reduce the search of possible candidates.