86 votos

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

Este problema me esta dando el momento más difícil:

Probar o refutar que hay un número de Fibonacci que termina con 2014 ceros.

Traté de inducción matemática (para más fuerte declaración que afirma que hay un número de Fibonacci que termina en un número de ceros), pero sin suerte hasta ahora.


Pregunta relacionada: resultados modulares de Fibonacci

79voto

Roger Hoover Puntos 56

Este es un clásico. La secuencia de Fibonacci $\pmod{m}$ es periódica para cualquier $m$, ya que hay sólo un número finito de elementos de $\mathbb{Z}_m\times\mathbb{Z}_m$, así que para dos números enteros $a,b$ tenemos que $\langle F_a,F_ {+1}\rangle\equiv\langle F_b,F_{b+1}\rangle \pmod{m}$ como consecuencia de la Dirichlet cuadro de principio. Sin embargo, la última condición implica $F_ {+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}$ es delimitada por $m^2$ ($m^2-1$ si tenemos cuidado lo suficiente como 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 coprime). Ahora basta tomar $m=10^{2014}$ y el aviso de que $F_0=0$ para demostrar que existe un 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 de $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),$$ de ello se sigue que: $$ \nu_5(F_k) = \nu_5(k), $$ por lo que $$u\leq 2^{4028}\cdot 5^{2014}=20^{2014}$$ por el teorema Chino. Pongo una prueba de la Oleg567 conjetura: $$ k\a mediados de F_n \quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n} $$ en una pregunta aparte. Desde $8=F_6\mid F_{750}$ (porque $6\mediados de 750$) y $\nu_5(750)=3$, tenemos que $1000|F_{750}$ y a través de la Oleg567 del lema obtenemos $$ u\leq \frac{3}{4}10^{2014}.$$

33voto

Gro-Tsen Puntos 1555

Podemos hacer un poco de la teoría algebraica de números. Deje que $\phi$ ser una raíz de $X^2 - X - 1$ más de $\mathbb{Q}$ ("golden ratio"), y vamos a trabajar en el campo de número de $\mathbb{Q}(\phi) = \mathbb{Q}(\sqrt{5})$ y su anillo de enteros de $\mathbb{Z}[\phi]$: llamamos a $v_2$ y $v_5$ las valoraciones de $\mathbb{Q}(\phi)$ que extender la costumbre de $2$-ádico y $5$-ádico valoraciones en $\mathbb{Q}$.

El $$n-ésimo 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 pregunta es la caracterización de los $n$ que $v_2(F_n) \geq 2014$ y $v_5(F_n) \geq 2014$ (y, por supuesto, mostrar que tal $n$). Ahora $\phi \phi' = 2\phi - 1 = \sqrt{5}$, por lo que claramente $v_2(\phi \phi') = 0$ y $v_5(\phi \phi') = \frac{1}{2}$. También, desde $\phi\phi' = 1$, es claro que $\phi\phi'$ son las unidades, por lo que $v_2(\phi) = v_2(\phi') = 0$ y $v_5(\phi) = v_5(\phi') = 0$.

Sobre $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$. Molesto, el $2$-ádico exponencial sólo converge (en unramified extensiones de $\mathbb{Q}_2$, aquí la finalización de $\mathbb{Q}(\phi)$ bajo $v_2$) por us $v_2(z)>1$, y tenemos que ir tan lejos como $n=6$ obtener $v_2(F_n) = 3 > 1$, después de lo que es claro que $v_2(\lambda^{6k}-1) = 3 + v_2(k)$ por la proposición II.5.5 de Neukirch de la Teoría Algebraica de números (que se citan a continuación; $e=1$ y $p=2$). Para $n$ no congruentes a $6$, entonces es fácil ver que $v_2(\lambda^n-1)$ es $1$ si $n$ es congruente a $3$ mod $6$ y $0$ si $n$ es congruente a $1,2,4,5$ mod $6$. Por lo que el $$ n para los cuales $v_2(F_n) \geq 2014$ son los múltiplos de $2^{2011} \times 6 = 2^{2012} \times 3$.

Sobre $v_5$, $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 es problemático debido a la ramificación es manso (en la notación de Neukirch de la citada proposición, $e=2$ y $p=5$): tenemos $v_5(\lambda^n-1) = \frac{1}{2} + v_5(n)$, que es de $v_5(F_n) = v_5(n)$ para todo $n$. Por lo que el $$ n para los cuales $v_5(F_n) \geq 2014$ son los múltiplos de $5^{2014}$.

Por lo tanto, poner esto juntos, el $n$ de los cuales $F_n$ termina 2014 con ceros son los múltiplos de $75\times 10^{2012}$. El primero es de $F_{n_0}$ donde $n_0 = 75\times 10^{2012}$.

Como un bono, pudimos demostrar que los últimos dígitos de $F_{n_0}$ antes de que el 2014 ceros son: $177449$.


Edit: Para su comodidad, aquí está la declaración de la proposición en Neukirch del libro que cito arriba:

Deje que $K|\mathbb{Q}_p$ $\mathfrak{p}$-ádico número de campo con la valoración anillo de $\mathcal{S}$ y el máximo ideal de $\mathfrak{p}$, y vamos a p $\mathcal{S} = \mathfrak{p}^e$ [Gro-Tsen nota: $p$ es el carácter residual, por lo que $e$ es la absoluta ramificación índice]. Entonces, el poder de la serie

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

y

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

rendimiento, por $n > \frac{e}{p-1}$, dos mutuamente inversas isomorphisms (y homeomorphisms)

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

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

Aplicamos esto a la finalización de $\mathbb{Q}(\phi)$ bajo $v_2$ o $v_5$. La conclusión a la que uso es que $v(\exp(x)-1) = v(x)$, o más bien, $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 calcular).

23voto

Oleg567 Puntos 9849

Sólo la 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í (Pisano Período) se dice, que la secuencia de los últimos $d$ dígitos de los números de Fibonacci tiene un período de $15·10^{d-1}$.
Nuestra $75\cdot 10^{d-2}$ es un medio período (sabiendo que $F_0=0$).


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

9voto

Jens Svendsen Puntos 16

Dado cualquier n (incluso uno con 2014 ceros a la derecha) tiene que ser los valores de b y k de modo 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 la mod n de los residuos para, finalmente, formar un ciclo de repetición, y se ha probado en otras respuestas).

Una vez que la b y k valores se encuentran, por los "dos saltos" de la identidad usando saltos de 1 y k a partir de índice de b obtenemos $F_bF_{b+k+1} = F_{b+1}F_{b+k} - (-1)^{b}F_kF_1$.

Ahora, note 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$ ha de 2014 ceros finales.

edit: se ha corregido un error tipográfico en el exponente de a (-1)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X