Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
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. –  Alex B. Dec 18 '10 at 12:07
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). –  George Lowther Dec 18 '10 at 17:08
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.pdf –  Weaam Dec 18 '10 at 18:42

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.