Fibonacci number that ends with 2014 zeros?

This problem is giving me the hardest time:

Prove or disprove that there is a Fibonacci number that ends with 2014 zeros.

I tried mathematical induction (for stronger statement that claims that there is a Fibonacci number that ends in any number of zeroes), but no luck so far.


Related question: Fibonacci modular results

Answer

This is a classic. The Fibonacci sequence \pmod{m} is periodic for any m, since there are only a finite number of elements in \mathbb{Z}_m\times\mathbb{Z}_m, so for two distinct integers a,b we must have \langle F_a,F_{a+1}\rangle\equiv\langle F_b,F_{b+1}\rangle \pmod{m} as a consequence of the Dirichlet box principle. However, the last condition implies F_{a+2}\equiv F_{b+2}\pmod{m} and, by induction, F_{a+k}\equiv F_{b+k}\pmod{m}. Hence the period of the Fibonacci sequence \pmod{m} is bounded by m^2 (m^2-1 if we are careful enough to notice that \langle F_c,F_{c+1}\rangle\equiv\langle0,0\rangle\pmod{m} is not possible since two consecutive Fibonacci numbers are always coprime). Now it suffices to take m=10^{2014} and notice that F_0=0 to prove that there exists an integer u\leq 10^{4028} such that F_u\equiv 0\pmod{m}, i.e. F_u ends with at least 2014 zeroes.

It is also possible to give better estimates for u.

Since F_k is divisible by 5 only when k is divisible by 5 and:

F_{5k} = F_k(25 F_k^4 + 25(-1)^k F_k^2 + 5),
it follows that:
\nu_5(F_k) = \nu_5(k),
so u\leq 2^{4028}\cdot 5^{2014}=20^{2014} by the Chinese theorem. I put a proof of the Oleg567 conjecture:
k\mid F_n \quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n}
in a separate question. Since 8=F_6\mid F_{750} (because 6\mid 750) and \nu_5(750)=3, we have that 1000|F_{750} and through the Oleg567’s lemma we get
u\leq \frac{3}{4}10^{2014}.

Attribution
Source : Link , Question Author : VividD , Answer Author : Community

Leave a Comment