Mostrar si n divide un número de Fibonacci solo., entonces se divide infinitamente muchos números de Fibonacci.

Question

Mostrar si n divide un número Fibonacci, entonces se divide infinitamente muchos números de Fibonacci.

Answer 1

En realidad, cada número entero distinto de cero $m$ divide infinitamente muchos números de Fibonacci.

Considerar la secuencia de Fibonacci modulo $m$. Todavía satisface la recurrencia $F_n\equiv F_{n-1}+F_{n-2}\pmod m$, y dado que hay sólo un número finito de posibles pares de $(F_{n-1},F_{n-2})$ se volverá a repetir pronto o más tarde.

Porque también tenemos $F_{n-2} \equiv F_n - F_{n-1} \pmod m$ podemos ejecutar la recurrencia hacia atrás, de modo que la repetición de parte de la secuencia se inicia a la derecha de $F_0$.

Desde $F_0=0$, habrá al menos un $F_i\equiv 0\pmod m$ por cada período de la repetición, es decir, una infinidad de veces.

Answer 2

De Wikipedia:

$$\gcd(F_m,F_n)=F_{\gcd(m,n)}$$

Así si $m\mid n$, $\gcd(m,n)=m$ % que $\gcd(F_m,F_n)=F_m$y $F_m\mid F_n$.

Por lo tanto si $d\mid F_n$, $d\mid F_{kn}$ % todos $k\in\Bbb N$.

Answer 3

Sugerencia $\,\ {\rm mod}\ n\!:\,$ el cambio de mapa $\ (f_i,f_{i-1})\mapsto (f_{i+1},f_i)$ es invertible mapa de $\,(a,b)\mapsto (a\!+\!b,a)\,$ sobre un conjunto finito, por lo que una permutación. Así, sus órbitas son ciclos (es decir, no tienen preperiodic parte). Por lo tanto, si $\,f_k\equiv 0\,$ $\,(0,f_{k-1})\,$ se produce en la órbita de $\,(f_1,f_0)$ por lo que este valor es tomado por una infinidad de $\,(f_j,f_{j-1}),\,$ cada vez que el mapa de los ciclos de vuelta en el mismo lugar en el ciclo finito.

Comentario $\ $ Tal cíclica de la estructura de la permutación de las órbitas a menudo es reinventado a partir de cero en casos concretos como este - que me refiero como reinventar la rueda (ciclo). Uno puede encontrar muchos ejemplos en mis anteriores posts (incluyendo problemas de competencia). He aquí un ejemplo típico:

> A sequence f(n) satisfies the relation f(n+2) = [f(n+1)]^2 - f(n), 
> with f(1) = 39 and f(2) = 45.  Prove that 1986 divides infinitely 
> many terms of the sequence. 

Desde la recursividad determina los valores únicos de $\rm\:f_{n+2},\:f_n\:$ cuando correr delante hacia atrás, el cambio de mapa en la secuencia induce una permutación $\rm\:F\:$ de enteros pares $$\rm mod\ \ 1986\!:\ \ F(f_n,f_{n+1})\ =\ (f_{n+1},f_{n+2})\quad i.e.\quad F(a,b)\: =\ (b,b^2-a)\ \ $$ Pero $\,0\,$ se produce en el ciclo que contiene a $\,(39,45)\,$ desde $\rm\:F(39,45) = (45,0),\,$ por lo $\,0\,$ se produce infinitamente a menudo en este ciclo finito al $\rm\,F\,$ es iterado.

Answer 4

Demostrar por inducción que $F_{km}\equiv0\pmod{F_k}$ % todos $m\ge1$.

Answer 5

Deje $S$ ser el operador de desplazamiento en los índices. A continuación, la recursividad de la Secuencia de Fibonacci es $$ 0=(S^2-S-1)F_n=(S-\phi)(S-(-1/\phi))F_n\etiqueta{1} $$ Desde $x-a\mid x^k-a^k$, también podemos $$ 0=\left(S^k-\phi^k\right)\left(S^k-(-1/\phi)^k\right)F_n=\left(S^2-\left(\phi^k+(-1/\phi)^k\right)S+(-1)^k\right)\tag{2} $$ Los Números de Lucas, $L_k$, que cumplen la misma definición de recursividad como los números de Fibonacci, están dadas por $$ L_k=\phi^k+(-1/\phi)^k\etiqueta{3} $$ Por lo tanto, combinando $(2)$$(3)$, tenemos $$ F_{n+2k}=L_kF_{n+k}+(-1)^{k-1}F_n\etiqueta{4} $$ Si establecemos $n=mk$, obtenemos $$ F_{(m+2)k}=L_kF_{(m+1)k}+(-1)^{k-1}F_{mk}\etiqueta{5} $$ Así, para cualquier $k$, tenemos una recursividad en el $k^{th}$ Números de Fibonacci. Desde $F_0=0$, la recursividad $(5)$ garantiza que $F_{mk}$ es divisible por $F_k$.