Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Where did you find this problem? –  anorton Jul 19 at 22:07
8  
Modular arithmetic. Also, $0$ is a fibonacci number. –  Hurkyl Jul 19 at 22:07
1  
@anorton In a high school math teacher's notes, a friend of mine. –  VividD Jul 19 at 22:16
1  
It seems that $F_{n}$ ends with $k$ zeroes ($k\ge 3$), where $n = 75 \cdot 10^{k-2}$. –  Oleg567 Jul 19 at 22:41
1  
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??? –  Oleg567 Jul 19 at 23:10

4 Answers 4

up vote 18 down vote accepted

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

share|improve this answer
    
Great answer! I am just not clear about digits 677449 - how exactly were they obtained? –  VividD Jul 21 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) –  Gro-Tsen Jul 21 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). –  Gro-Tsen Jul 21 at 1:19
1  
All answers are good, but I liked this the most. –  VividD Jul 23 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$). –  Gro-Tsen Jul 23 at 15:11

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

share|improve this answer
    
Wait, how does the congruence of the gcd's of two pairs of integers lead to the congruence of the sums of each pair? –  Nishant Jul 19 at 22:22
1  
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 at 23:45
1  
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. –  Jack D'Aurizio Jul 20 at 0:22
6  
@Yann: the Fibonacci recurrence is reversible, so showing that the Fibonacci sequence is eventually periodic shows that it's always periodic. –  Qiaochu Yuan Jul 20 at 3:56
2  
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. –  Steven Stadnicki Jul 20 at 4:01

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

share|improve this answer
1  
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. –  Lubin Jul 20 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)

share|improve this answer
1  
This is so far the shortest and the most elegant answer/proof. –  VividD Jul 22 at 7:21
1  
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. –  VividD Jul 22 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[1]$ –  Random Excess Jul 22 at 8:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.