Hace $\,m\mid n$ si $ F_m\mid F_n$ ?

Question

Los números de Fibonacci $F_n$ se definen como $$F_1=1, \; F_2=1, \; F_{n+1} = F_n+F_{n-1},\; n\ge 2. $$

Eso es, $$ 1,1,2,3,5,8,13, \dots$$

Tenga en cuenta que, por ejemplo, $F_4=3$ divide $F_8=21$ y $F_{12}=144.$

¿Es cierto que para todos los enteros positivos $m$ y $n$ $$m\mid n \iff F_m\mid F_n ?$$

Answer 1

Mi técnica favorita de Fibonacci es el formulación de la matriz que vale la pena conocer y fácilmente comprobable : $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$

Si $n=mk$ entonces $$ \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} =\begin{pmatrix}1&1\\1&0\end{pmatrix}^{n} =\begin{pmatrix}1&1\\1&0\end{pmatrix}^{mk} = \left(\begin{pmatrix}1&1\\1&0\end{pmatrix}^{m}\right)^k = \begin{pmatrix}F_{m+1}&F_m\\F_m&F_{m-1}\end{pmatrix}^k \quad (*) $$ Now note that $$ \begin{pmatrix} a & b \\ b & c\end{pmatrix} \begin{pmatrix} A & B \\ D & C\end{pmatrix} = \begin{pmatrix} a A + b D & a B + b C \\ A b + c D & b B + c C\end{pmatrix} $$ y mira el $(1,2)$ entradas en (*) para concluir por inducción en $k$ que el $(1,2)$ entrada en ese $k$ -la potencia es un múltiplo de $F_m$ .

(O simplemente anotar que, mod $F_m$ la matriz del lado derecho es diagonal y también lo son todas sus potencias).

Answer 2

Lo sabemos:

$F_n=\frac{1}{\sqrt5}[(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n]$

Ahora $m | n$ ⇒ $n = km$

$a^{n}-b^{n}=(a^m)^k-(b^m)^k=k_1(a^m-b^m)$

Donde $a=(\frac{1+\sqrt5}{2})$ y $b=(\frac{1-\sqrt5}{2})$

Es decir $F_m | F_n$ .

Tenga en cuenta que :

$(a^p-b^p)=(a-b)( a^{p-1}+a^{p-2}b+a^{p-3}b^2+ . . .a^2 b^{p-3}+a b^{p-2}+ b^{p-1})$

Aquí $k_1= a^{p-1}+a^{p-2}b+a^{p-3}b^2+ . . .a^2 b^{p-3}+a b^{p-2}+ b^{p-1}$

Así que $k_1$ es un número entero.

Answer 3

Una forma fácil de ver esto es observando la secuencia de Fibonacci mod $F_m$ . Ahora $F_{m+1}\equiv kF_1$ (mod $F_m$ ) para algunos $k$ y $F_m\equiv kF_0\equiv 0$ . Así podemos demostrar por inducción que $F_{m+i}\equiv kF_i$ (mod $F_m$ ) para cada $i\geq 0$ y en particular $F_{jm}\equiv kF_{(j-1)m}$ por cada $j\geq 1$ . Se deduce por inducción que $F_{jm}\equiv 0$ (mod $F_m$ ) para cada $j$ .