# Finding the smallest prime number that divides $Fib(n)$ but not any other $Fib(k)$ smaller than $Fib(n)$

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.

-
What's $F$ supposed to be? – J. M. Dec 18 '10 at 10:58
@J.M: I just added the definition of $F$ :) – Quixotic Dec 18 '10 at 11:00
Not to compute $F(n)$ is an artificial constraint that doesn't make any sense from an algorithmic point of view. Computing $F(n)$ will be the computationally least intensive task. Factorising it is more more intensive, but that can indeed be avoided in many cases. – Alex B. Dec 18 '10 at 12:07
And, of course, there need not be any such p. The only prime factor of F(6)=8 is 2, which divides F(3). – George Lowther Dec 18 '10 at 17:08
@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.pdf – Weaam Dec 18 '10 at 18:42

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.

-