Fibonacci number that ends with 2014 zeros?

Question

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 1

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}.$$

Answer 2

We can do a little algebraic number theory. Let $\phi$ be a root of $X^2 - X - 1$ over $\mathbb{Q}$ ("golden ratio"), and let us work in the number field $\mathbb{Q}(\phi) = \mathbb{Q}(\sqrt{5})$ and its ring of integers $\mathbb{Z}[\phi]$: we call $v_2$ and $v_5$ the valuations of $\mathbb{Q}(\phi)$ which extend the usual $2$-adic and $5$-adic valuations on $\mathbb{Q}$.

The $n$-th Fibonacci number is

$$F_n = \frac{\phi^n - \phi^{\prime n}}{\phi - \phi'}$$

where $\phi' = 1-\phi$ is the conjugate of $\phi$. The question is to characterize the $n$ for which $v_2(F_n) \geq 2014$ and $v_5(F_n) \geq 2014$ (and, of course, show that such an $n$ exists). Now $\phi - \phi' = 2\phi - 1 = \sqrt{5}$, so clearly $v_2(\phi - \phi') = 0$ and $v_5(\phi - \phi') = \frac{1}{2}$. Also, since $\phi\phi' = 1$, it is clear that $\phi,\phi'$ are units, so $v_2(\phi) = v_2(\phi') = 0$ and $v_5(\phi) = v_5(\phi') = 0$.

Concerning $v_2$, we now have $v_2(F_n) = v_2(\phi^n - \phi^{\prime n}) = v_2(\lambda^n-1)$ where $\lambda = \phi'/\phi = \phi - 2$. Annoyingly, the $2$-adic exponential only converges (on unramified extensions of $\mathbb{Q}_2$, here the completion of $\mathbb{Q}(\phi)$ under $v_2$) for $v_2(z)>1$, and we have to go as far as $n=6$ to get $v_2(F_n) = 3 > 1$, after what it is clear that $v_2(\lambda^{6k}-1) = 3 + v_2(k)$ by proposition II.5.5 of Neukirch's Algebraic Number Theory (quoted below; here $e=1$ and $p=2$). For $n$ not congruent to $6$, it is then easy to see that $v_2(\lambda^n-1)$ is $1$ if $n$ is congruent to $3$ mod $6$ and $0$ if $n$ is congruent to $1,2,4,5$ mod $6$. So the $n$ for which $v_2(F_n) \geq 2014$ are the multiples of $2^{2011} \times 6 = 2^{2012} \times 3$.

Concerning $v_5$, have $v_5(F_n) = -\frac{1}{2} + v_5(\phi^n - \phi^{\prime n}) = -\frac{1}{2} + v_5(\lambda^n-1)$. This time, convergence of the exponential is unproblematic because ramification is tame (in the notation of Neukirch's above-quoted proposition, $e=2$ and $p=5$): we have $v_5(\lambda^n-1) = \frac{1}{2} + v_5(n)$, that is $v_5(F_n) = v_5(n)$, for every $n$. So the $n$ for which $v_5(F_n) \geq 2014$ are the multiples of $5^{2014}$.

So, putting this together, the $n$ for which $F_n$ ends with 2014 zeroes are the multiples of $75\times 10^{2012}$. The first one is $F_{n_0}$ where $n_0 = 75\times 10^{2012}$.

As a bonus, we could show that the last few digits of $F_{n_0}$ before the 2014 zeroes are: $177449$.

---

Edit: For convenience, here is the statement of the proposition in Neukirch's book that I quote above:

Let $K|\mathbb{Q}_p$ be a $\mathfrak{p}$-adic number field with valuation ring $\mathcal{O}$ and maximal ideal $\mathfrak{p}$, and let $p\mathcal{O} = \mathfrak{p}^e$ [Gro-Tsen's note: $p$ is the residual characteristic, so $e$ is the absolute ramification index]. Then the power series

$$\exp(x) = 1 + x + \frac{x^2}{2} + \frac{x^3}{3!} + \cdots$$

and

$$\log(1+z) = z - \frac{z^2}{2} + \frac{z^3}{3} - \cdots$$

yield, for $n > \frac{e}{p-1}$, two mutually inverse isomorphisms (and homeomorphisms)

$$\mathfrak{p}^n \overset{\exp}{\underset{\log}{\mathop{\rightleftarrows}}} U^{(n)}$$

[Gro-Tsen's note: $\mathfrak{p}^n$ is the set of elements with valuation $v(x) \geq n/e$ (normalized by $v(p) = 1$), and $U^{(n)} = 1 + \mathfrak{p}^n$ is the set of $z$ such that $v(z-1) \geq n/e$.]

We apply this to the completion of $\mathbb{Q}(\phi)$ under $v_2$ or $v_5$. The conclusion we use is that $v(\exp(x)-1) = v(x)$, or rather, $v(c^x - 1) = v(x) + v(\log c)$ (where $c$ is $\lambda^6$ in the case of $v_2$ and $\lambda$ in the case of $v_5$, and $v(\log c)$ is a constant we compute).

Answer 3

Just observation: $$F_{750}\equiv 0 \pmod{1000}$$ $$F_{7500}\equiv 0 \pmod{10000}$$ $$F_{75000}\equiv 0 \pmod{100000}$$ $$F_{750000}\equiv 0 \pmod{1000000}$$ $$F_{7500000}\equiv 0 \pmod{10000000}$$

---

Here (Pisano Period) is said, that the sequence of last $d$ digits of Fibonacci numbers has a period of $15·10^{d-1}$.
Our $75\cdot 10^{d-2}$ is a half-period (knowing that $F_0=0$).

---

I think must be some property of Fibonacci numbers: $$ \large{ k|F_n \quad \Rightarrow \quad k^d|F_{k^{d-1}n}. }$$

Answer 4

Given any n (even one with 2014 trailing zeros) there has to be values b and k so that $F_b\equiv F_{b+k} \pmod{n}$ AND $F_{b+1}\equiv F_{b+k+1} \pmod{n}$ (which is equivalent to the claim the mod n residues have to eventually form a repeating cycle, and proven in other answers).

Once such b and k values are found, by the "two hop" identity using hops of 1 and k starting from index b we get $F_bF_{b+k+1} = F_{b+1}F_{b+k} - (-1)^{b}F_kF_1$.

Now, notice that $F_bF_{b+k+1}\equiv F_{b+1}F_{b+k} \pmod{n}$ by construction, so it must be $F_k\equiv 0 \pmod{n}$, that is, $F_k$ has 2014 trailing zeroes.

edit: corrected typo on exponent to (-1)

Answer 5

Let $\ell_n$ be the last $2014$ digits of of the $n$th of the Fibonacci sequence. Note if we know $\ell_{k+1}$ and $\ell_k$, then we know $\ell_{k-1}$. So if for two natural numbers $n,k$ we find that $\ell_n=\ell_{n+k}$ and $\ell_{k+1}=\ell_{n+k+1}$, then it follows that $$\begin{align*}\ell_{k-1}&=\ell_{n+k-1}\\\ell_{k-2}&=\ell_{n+k-2} \\ &\dots \\\ell_1&=\ell_{n+1} \end{align*}$$And since $\ell_1=0$, it follows that $\ell_{n+1}=0$ and hence the $(n+1)$st Fibonacci number will end in $2014$ zeroes.

Now let us prove that such a number exists. Consider the following pairs: $$\begin{align*} \ell_1&,\ell_2 \\ \ell_{2}&,\ell_3 \\ &\vdots \\ \ell_{10^{48}}&, \ell_{10^{48}+1} \\ \ell_{10^{48}+1}&, \ell_{10^{48}+2} \end{align*}$$Since there are $\left({10^{24}}\right)^2$ different values of the pairs, by the Pigeonhole Principle, there exists $i,j$ where $1<i<j\leq 10^{48}+1$ such $\ell_{i}=\ell_{j}$ and $\ell_{i+1}=\ell_{j+1}$. It follows that $(\ell_1,\ell_2)=(\ell_{j-i+1},\ell_{j-i})$ hence the $j-i+1$st Fibonacci number ends in $2014$ zeroes.