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.

  • 0
    What's $F$ supposed to be?2010-12-18
  • 0
    @J.M: I just added the definition of $F$ :)2010-12-18
  • 0
    Better. It's hard for things like "F(n)" to pop up in search engine results, unlike terms like "Fibonacci". ;)2010-12-18
  • 3
    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.2010-12-18
  • 1
    And, of course, there need not be any such p. The only prime factor of F(6)=8 is 2, which divides F(3).2010-12-18
  • 0
    George Lowther:Yes, I know there can be such cases.2010-12-18
  • 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.