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
    @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