¿Número de Fibonacci que termina con 2014 ceros?

Question

Este problema es el que más me cuesta:

Demuestra o refuta que existe un número de Fibonacci que termina en 2014 ceros.

Intenté la inducción matemática (para la afirmación más fuerte que afirma que hay un número de Fibonacci que termina en cualquier número de ceros), pero no hubo suerte hasta ahora.

---

Pregunta relacionada: Resultados modulares de Fibonacci

Answer 1

Esto es un clásico. La secuencia de Fibonacci $\pmod{m}$ es periódica para cualquier $m$ ya que sólo hay un número finito de elementos en $\mathbb{Z}_m\times\mathbb{Z}_m$ por lo que para dos enteros distintos $a,b$ debemos tener $\langle F_a,F_{a+1}\rangle\equiv\langle F_b,F_{b+1}\rangle \pmod{m}$ como consecuencia del principio de caja de Dirichlet. Sin embargo, la última condición implica $F_{a+2}\equiv F_{b+2}\pmod{m}$ y, por inducción, $F_{a+k}\equiv F_{b+k}\pmod{m}$ . Por lo tanto, el período de la secuencia de Fibonacci $\pmod{m}$ está limitada por $m^2$ ( $m^2-1$ si somos lo suficientemente cuidadosos para notar que $\langle F_c,F_{c+1}\rangle\equiv\langle0,0\rangle\pmod{m}$ no es posible ya que dos números de Fibonacci consecutivos son siempre coprimos). Ahora basta con tomar $m=10^{2014}$ y observe que $F_0=0$ para demostrar que existe un número entero $u\leq 10^{4028}$ tal que $F_u\equiv 0\pmod{m}$ es decir $F_u$ termina con al menos $2014$ ceros.

También es posible dar mejores estimaciones para $u$ .

Desde $F_k$ es divisible por $5$ sólo cuando $k$ es divisible por $5$ y:

$$ F_{5k} = F_k(25 F_k^4 + 25(-1)^k F_k^2 + 5),$$ se deduce que: $$ \nu_5(F_k) = \nu_5(k), $$ así que $$u\leq 2^{4028}\cdot 5^{2014}=20^{2014}$$ por el teorema chino. Puse una prueba de la conjetura Oleg567: $$ k\mid F_n \quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n} $$ en un pregunta separada . Desde $8=F_6\mid F_{750}$ (porque $6\mid 750$ ) y $\nu_5(750)=3$ tenemos que $1000|F_{750}$ y mediante el lema de Oleg567 obtenemos $$ u\leq \frac{3}{4}10^{2014}.$$

Answer 2

Podemos hacer un poco de teoría algebraica de números. Sea $\phi$ sea una raíz de $X^2 - X - 1$ en $\mathbb{Q}$ ("proporción áurea"), y trabajemos en el campo numérico $\mathbb{Q}(\phi) = \mathbb{Q}(\sqrt{5})$ y su anillo de enteros $\mathbb{Z}[\phi]$ : llamamos a $v_2$ y $v_5$ las valoraciones de $\mathbb{Q}(\phi)$ que amplían los habituales $2$ -adic y $5$ -Valoraciones periódicas sobre  $\mathbb{Q}$ .

El $n$ -El número de Fibonacci es

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

donde $\phi' = 1-\phi$ es el conjugado de $\phi$ . La cuestión es caracterizar el $n$ para lo cual $v_2(F_n) \geq 2014$ y $v_5(F_n) \geq 2014$ (y, por supuesto, demostrar que tal $n$ existe). Ahora $\phi - \phi' = 2\phi - 1 = \sqrt{5}$ , así que claramente $v_2(\phi - \phi') = 0$ y $v_5(\phi - \phi') = \frac{1}{2}$ . Además, como $\phi\phi' = 1$ es evidente que $\phi,\phi'$ son unidades, por lo que $v_2(\phi) = v_2(\phi') = 0$ y $v_5(\phi) = v_5(\phi') = 0$ .

Con respecto a $v_2$ Ahora tenemos $v_2(F_n) = v_2(\phi^n - \phi^{\prime n}) = v_2(\lambda^n-1)$ donde $\lambda = \phi'/\phi = \phi - 2$ . Molestamente, el $2$ -exponencial de los ádicos sólo converge (en extensiones no ramificadas de $\mathbb{Q}_2$ Aquí, la finalización de $\mathbb{Q}(\phi)$ en  $v_2$ ) para $v_2(z)>1$ y tenemos que ir tan lejos como $n=6$ para conseguir $v_2(F_n) = 3 > 1$ Después de lo que está claro que $v_2(\lambda^{6k}-1) = 3 + v_2(k)$ por la proposición II.5.5 de Neukirch Teoría algebraica de los números (citado más abajo; aquí $e=1$ y $p=2$ ). Para $n$ no es congruente con $6$ es fácil ver entonces que $v_2(\lambda^n-1)$ es $1$ si $n$ es congruente con $3$ mod  $6$ y $0$ si $n$ es congruente con $1,2,4,5$ mod  $6$ . Así que el $n$ para lo cual $v_2(F_n) \geq 2014$ son los múltiplos de $2^{2011} \times 6 = 2^{2012} \times 3$ .

Con respecto a $v_5$ , tienen $v_5(F_n) = -\frac{1}{2} + v_5(\phi^n - \phi^{\prime n}) = -\frac{1}{2} + v_5(\lambda^n-1)$ . Esta vez, la convergencia de la exponencial no es problemática porque la ramificación es dócil (en la notación de la proposición de Neukirch antes citada, $e=2$ y $p=5$ ): tenemos $v_5(\lambda^n-1) = \frac{1}{2} + v_5(n)$ Es decir $v_5(F_n) = v_5(n)$ para cada  $n$ . Así que el $n$ para lo cual $v_5(F_n) \geq 2014$ son los múltiplos de $5^{2014}$ .

Así que, juntando todo esto, el $n$ para lo cual $F_n$ termina con 2014 ceros son los múltiplos de $75\times 10^{2012}$ . El primero es $F_{n_0}$ donde $n_0 = 75\times 10^{2012}$ .

Como extra, podríamos demostrar que los últimos dígitos de $F_{n_0}$ antes de los ceros de 2014 son: $177449$ .

---

Editar: Para mayor comodidad, aquí está el enunciado de la proposición en el libro de Neukirch que cito arriba:

Dejemos que $K|\mathbb{Q}_p$ ser un $\mathfrak{p}$ -campo numérico adico con anillo de valoración $\mathcal{O}$ y el ideal máximo $\mathfrak{p}$ y que $p\mathcal{O} = \mathfrak{p}^e$ [Nota de Gro-Tsen: $p$ es la característica residual, por lo que $e$ es el índice de ramificación absoluto]. Entonces la serie de potencias

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

et

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

rendimiento, para $n > \frac{e}{p-1}$ dos isomorfismos (y homeomorfismos) mutuamente inversos

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

[Nota de Gro-Tsen: $\mathfrak{p}^n$ es el conjunto de elementos con valoración $v(x) \geq n/e$ (normalizado por $v(p) = 1$ ), y $U^{(n)} = 1 + \mathfrak{p}^n$ es el conjunto de $z$ tal que $v(z-1) \geq n/e$ .]

Lo aplicamos a la realización de $\mathbb{Q}(\phi)$ en $v_2$ o $v_5$ . La conclusión que utilizamos es que $v(\exp(x)-1) = v(x)$ o mejor dicho, $v(c^x - 1) = v(x) + v(\log c)$ (donde $c$ es $\lambda^6$ en el caso de $v_2$ y $\lambda$ en el caso de $v_5$ y $v(\log c)$ es una constante que calculamos).

Answer 3

Sólo una observación: $$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}$$

---

Aquí (Período Pisano) se dice que la secuencia de la última $d$ dígitos de los números de Fibonacci tiene un período de $15·10^{d-1}$ .
Nuestro $75\cdot 10^{d-2}$ es un medio período (sabiendo que $F_0=0$ ).

---

Creo que debe ser alguna propiedad de los números de Fibonacci: $$ \large{ k|F_n \quad \Rightarrow \quad k^d|F_{k^{d-1}n}. }$$

Answer 4

Dado cualquier n (incluso uno con 2014 ceros al final) tiene que haber valores b y k para que $F_b\equiv F_{b+k} \pmod{n}$ Y $F_{b+1}\equiv F_{b+k+1} \pmod{n}$ (que es equivalente a la afirmación de que los residuos mod n tienen que formar eventualmente un ciclo repetitivo, y que se ha demostrado en otras respuestas).

Una vez encontrados dichos valores b y k, por la identidad de "dos saltos" utilizando saltos de 1 y k partiendo del índice b obtenemos $F_bF_{b+k+1} = F_{b+1}F_{b+k} - (-1)^{b}F_kF_1$ .

Ahora, fíjate que $F_bF_{b+k+1}\equiv F_{b+1}F_{b+k} \pmod{n}$ por construcción, por lo que debe ser $F_k\equiv 0 \pmod{n}$ Es decir, $F_k$ tiene 2014 ceros finales.

edit: corregida la errata del exponente a (-1)

Answer 5

Dejemos que $\ell_n$ ser el último $2014$ dígitos de la $n$ de la secuencia de Fibonacci. Obsérvese que si conocemos $\ell_{k+1}$ y $\ell_k$ entonces sabemos que $\ell_{k-1}$ . Entonces, si para dos números naturales $n,k$ encontramos que $\ell_n=\ell_{n+k}$ y $\ell_{k+1}=\ell_{n+k+1}$ entonces se deduce que $$\begin{align*}\ell_{k-1}&=\ell_{n+k-1}\\\ell_{k-2}&=\ell_{n+k-2} \\ &\dots \\\ell_1&=\ell_{n+1} \end{align*}$$ Y como $\ell_1=0$ se deduce que $\ell_{n+1}=0$ y por lo tanto el $(n+1)$ El primer número de Fibonacci terminará en $2014$ ceros.

Ahora demostremos que tal número existe. Consideremos los siguientes pares: $$\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*}$$ Dado que hay $\left({10^{24}}\right)^2$ diferentes valores de los pares, por el Principio de la Colocación, existe $i,j$ donde $1<i<j\leq 10^{48}+1$ tal $\ell_{i}=\ell_{j}$ y $\ell_{i+1}=\ell_{j+1}$ . De ello se desprende que $(\ell_1,\ell_2)=(\ell_{j-i+1},\ell_{j-i})$ de ahí que el $j-i+1$ El primer número de Fibonacci termina en $2014$ ceros.