1
$\begingroup$

We have a number $k$ and we have to find the smallest Fibonacci number that has common factor with it(except $1$). We also have $2 \leq k \leq 1,000,000$.

The required Fibonacci number is guaranteed to be less than $10^{18}$.

  • 7
    There are less than a hundred Fibonacci numbers below $10^{18}$. Just try them one by one.2012-06-25

1 Answers 1

2

Find all the primes dividing $k$. Run the Fibonacci recursion modulo each of these primes. See which gives you zero first. For example, if $k=667=23\times29$, the sequence reduced modulo 23 goes $$1,1,2,3,5,8,13,21,11,9,20,6,3,9,12,21,10,8,18,3,21,1,22,0$$ so the 24th Fibonacci number is a multiple of 23; modulo 29, you get $$1,1,2,3,5,8,13,21,5,26,2,28,1,0$$ so the 14th Fibonacci is a multiple of 29. $14\lt24$, so the 14th Fibonacci (which is $377=13\times29$) is the first one with a nontrivial common factor with $k$.

  • 0
    Note in particular that for any prime $p$, some $F_k$ with $k \le p+1$ is divisible by $p$.2012-06-26
  • 0
    If $p=5$, the first $k=5$; otherwise it is a divisor of $p-1$ if $p \equiv \pm 1 \mod 5$, or a divisor of $p+1$ if $p \equiv \pm 2 \mod 5$.2012-06-26
  • 0
    See also http://oeis.org/A0016022012-06-26
  • 0
    Sir please help me for this question, please describe this answer for me. How are you generate that list 1,1,2,3,5,8,13,21,11,9,20,6,3,9,12,21,10,8,18,3,21,1,22,0 Please Thanks in Advance2013-08-27
  • 0
    @Ajay, if you have a question, post a question. Don't hide it as a comment on an answer to someone else's question.2013-08-27