Números de Fibonacci divisibles por $9$

Question

En $n$ º número de Fibonacci $F_n$ se define del siguiente modo, $$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ Quiero saber cuántos de los primeros $1000$ Los números de Fibonacci son divisibles por $9$ ? ¿Es posible clasificar todos los números de Fibonacci divisibles por $9$ ?

He buscado en Google y he encontrado en un artículo que dice que cada $12$ es divisible por $9$ pero no se aporta ninguna prueba. ¿Son éstas las únicas cifras de este tipo? Cualquier idea para la solución sería útil.

Answer 1

Los números de Fibonacci $\bmod\ 9$ produce $$ \color{#C00000}{0,1,}1,2,3,5,8,4,3,7,1,8,\color{#0000FF}{0,8,}\dots\tag{1} $$ Como los términos azules son el negativo de los rojos, obtenemos $$ F_{n+12}\equiv-F_n\pmod{9}\tag{2} $$ Dado que el único número de Fibonacci en el primer $12$ es decir $0\bmod9$ es $F_0$ obtenemos $$ F_n\equiv0\pmod{9}\Longleftrightarrow n\equiv0\pmod{12}\tag{3} $$ Por lo tanto, $84$ de la primera $1000$ Los números de Fibonacci son divisibles por $9$ si comienza con $F_0$ pero si empiezas con $F_1$ sólo $83$ de la primera $1000$ son.

Answer 2

Sabemos por aquí , aquí o aquí , $F_m\mid F_n \iff m\mid n$ o $m=2$

ahora $F_{12}=144$ Así que.., $144\mid F_{12k}$ donde $k$ es un número natural.

En $F_{12k}\equiv 0\pmod 9$ y si $F_{12k-1}\equiv a\pmod 9, (a,9)=1$ como $(F_m,F_{m+1})=1$

Así que.., $F_{12k+1}\equiv (a+0)\pmod 9\equiv a\cdot F_1$ $F_{12k+2}\equiv (a+a)\pmod 9\equiv a\cdot F_2 ,$ $F_{12k+3}\equiv (2a+a)\pmod 9\equiv a\cdot F_3$ y así sucesivamente hasta $F_{12k+11}\equiv a\cdot F_{11}$

otra vez, $F_{12k-2}=F_{12k}-F_{12k-1}\equiv 0-a\pmod 9\equiv -a\cdot F_1,$ $F_{12k-3}\equiv -a-a\pmod 9\equiv -a\cdot F_2$ y así sucesivamente hasta $F_{12k-11}\equiv -a\cdot F_{10}$

Como observó Hendrik Jan, el período es $24$ ,

así que $9\mid F_n\iff 12\mid n$

Por lo tanto, el número de Fibonacci necesario es $\lfloor \frac{1000}{12}\rfloor=83$

Answer 3

Primero, probemos si $n$ divisible por $m$ entonces $F_n$ también es divisible por $F_m$ . Para demostrarlo necesitamos la fórmula $$\Large{F_{n+k} = F_{k+1} \cdot F_n + F_k \cdot F_{n-1}} \; (1) $$

Por lo tanto, $F_{2n} = F_{n+1} F_n + F_n F_{n-1}$ es divisible por $F_n$ y $F_{3n} = F_{2n + n} = F_{2n+1} F_n + F_{2n} F_{n-1}$ es divisible por $F_n$ etc.

Utilizando el método de inducción, supongamos $F_{k \cdot n}$ es divisible por $F_n$ Por lo tanto, $$\Large{F_{(k+1)n} = F_{kn +n} = F_{n+1} F_{kn} + F_n F_{kn-1}} \; (2) $$ también es divisible por $F_n$ .

Ahora, tenemos que encontrar todos los números de Fibonacci que son divisibles por 9. El primer número de Fibonacci que es divisible por 9 es $F_{12}=144$ .

Por lo tanto, $F_{12n}$ es divisible por 9.

Ahora demostremos que no hay ningún otro número de Fibonacci que sea divisible por 9.

$$ \begin{array}{|c|c|} \hline F_{1} \equiv 1 \; (mod \; 9) & F_{13} \equiv 8 \; (mod \; 9) \\ F_{2} \equiv 1 \; (mod \; 9) & F_{14} \equiv 8 \; (mod \; 9) \\ F_{3} \equiv 2 \; (mod \; 9) & F_{15} \equiv 7 \; (mod \; 9) \\ F_{4} \equiv 3 \; (mod \; 9) & F_{16} \equiv 6 \; (mod \; 9) \\ F_{5} \equiv 5 \; (mod \; 9) & F_{17} \equiv 4 \; (mod \; 9) \\ F_{6} \equiv 8 \; (mod \; 9) & F_{18} \equiv 1 \; (mod \; 9) \\ F_{7} \equiv 4 \; (mod \; 9) & F_{19} \equiv 5 \; (mod \; 9) \\ F_{8} \equiv 3 \; (mod \; 9) & F_{20} \equiv 6 \; (mod \; 9) \\ F_{9} \equiv 7 \; (mod \; 9) & F_{21} \equiv 2 \; (mod \; 9) \\ F_{10} \equiv 1 \; (mod \; 9) & F_{22} \equiv 8 \; (mod \; 9) \\ F_{11} \equiv 8 \; (mod \; 9) & F_{23} \equiv 1 \; (mod \; 9) \\ F_{12} \equiv 0 \; (mod \; 9) & F_{24} \equiv 0 \; (mod \; 9) \\ \hline \end{array}$$

Continuará en la misma secuencia. Lo que significa que sólo $F_{12n}$ es divisible por 9.

---

Prove (1) using induction, also.