# 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

• Where did you find this problem? Jul 19, 2014 at 22:07
• Modular arithmetic. Also, $0$ is a fibonacci number.
– user14972
Jul 19, 2014 at 22:07
• @anorton In a high school math teacher's notes, a friend of mine. Jul 19, 2014 at 22:16
• It seems that $F_{n}$ ends with $k$ zeroes ($k\ge 3$), where $n = 75 \cdot 10^{k-2}$. Jul 19, 2014 at 22:41
• Just computations. One idea is to prove this statement (if it is true): $$k|F_n \Rightarrow k^d|F_{k^{d-1}n}.$$ But how to prove??? Jul 19, 2014 at 23:10

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

• Unless I'm missing something, your argument shows that the sequence $(F_n)$ is ultimately periodic mod $m$. I fail to see how you can conclude that $F_n = 0$ mod $m$ for some $n > 0$.
– Yann
Jul 19, 2014 at 23:45
• Since $F_0\equiv 0\pmod{m}$ for every $m$, given that $\phi(m)$ is the period of the Fibonacci sequence $\pmod{m}$, then $F_{\phi(m)}\equiv 0\pmod{m}$. It is more or less a proof of the Fermat little theorem in disguise. Jul 20, 2014 at 0:22
• @Yann: the Fibonacci recurrence is reversible, so showing that the Fibonacci sequence is eventually periodic shows that it's always periodic. Jul 20, 2014 at 3:56
• I've swapped out parentheses for angle brackets in your ordered pairs to try and ameliorate some of the confusion - if you'd rather they were parens then by all means feel free to swap them back, but I think it's a little clearer this way. Jul 20, 2014 at 4:01
• Since you have not used any property of m, it means it is possible to replace $10^{2014}$ with any positive number, isn't it? Thus, for any integer there are infinitely many Fibonacci numbers which are divisible by it... Sounds cool but strange. May 20, 2017 at 1:08

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).

• Great answer! I am just not clear about digits 677449 - how exactly were they obtained? Jul 21, 2014 at 0:23
• @VividD: Concerning the digits before the zeros, the point is that $(c^x-1)/x$ tends to $\log c$ when $x\to0$ (if $c$ is a $\mathfrak{p}$-adic sufficiently close to $1$, as in the end of my answer). That and the expressions for $F_n$ easily imply that if $n=75\times 10^k$ then $F_n/10^{k+2}$ converges $2$-adically and $5$-adically (hence, "$10$-adically") when $k$ is an integer tending to $+\infty$. And we can compute their limits (something like $(\log(\lambda^6)/(\phi-\phi'))/8$). (continued) Jul 21, 2014 at 1:12
• (cont.) Now of course, I cheated: knowing that the 10-adic limit exists, i.e., that the last digits of $F_n/10^{k+2}$ stabilize, I just computed the first few values and got the value from there. But it wouldn't be very difficult to work out the error bounds explicitly. (This is why I wrote "we could show".) Of course, one needs a computer algebra software or a great deal of patience to actually compute $F_{75000}$, if only in a $2$- and $5$-adic approximation (or some expression involving $p$-adic logs). Jul 21, 2014 at 1:19
• All answers are good, but I liked this the most. Jul 23, 2014 at 14:31
• @VividD: Here's an extra comment you might like: the function $\mathbb{Z}\to\mathbb{Z}$ defined by $n\mapsto F_{3n}$ extends uniquely to a continuous and indeed analytic function $\mathbb{Z}_2\to\mathbb{Z}_2$. The same holds for $n\mapsto F_{4n}$ giving $\mathbb{Z}_5\to\mathbb{Z}_5$. I think it's an interesting exercise in $\mathfrak{p}$-adics to show this (and to consider where the $3$ and $4$ come from, and to compute their derivatives at $0$). Jul 23, 2014 at 15:11

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

• All of this must be known to Fib specialists, but that term doesn’t apply to me. By a cumbersome $p$-adic computation ($p=2,5$), I seem to have shown that for $m\ge3$, $2^m|F_k$ if and only if $3\cdot2^{m-2}|k$. And that $5^m|F_k$ if and only if $5^m|k$. This would show that your $750$, etc. are the smallest numbers satisfying the desired conditions. Jul 20, 2014 at 13:45

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)

• This is so far the shortest and the most elegant answer/proof. Jul 22, 2014 at 7:21
• I couldn't find what "two hop" identity is, however d'Ocagne's identity $F_nF_{m+1} = F_{n+1}F_{m} + (-1)^{m}F_{n-m}$ can be equivalently used. Jul 22, 2014 at 7:38
• Yes, that is just the special case where one of the hops is of length 1 and the other is n-m from a starting point of m and rearranged. $F[m]F[n+1] = F[m+1]F[n] - (-1)^{m}F[n-m]F$ Jul 22, 2014 at 8:35

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.