Skip to main content
1 of 5
Gro-Tsen
  • 6.6k
  • 27
  • 70

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 (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) = 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: $677449$.

Gro-Tsen
  • 6.6k
  • 27
  • 70