Propiedades de divisibilidad de Fibonacci $ F_n\mid F_{kn},\,$ $\, \gcd(F_n,F_m) = F_{\gcd(n,m)}$

Question

¿Puede alguien dar una generalización de las siguientes propiedades en una sola prueba? He comprobado los resultados, que he dado a continuación por el método de ensayo y error. Estoy buscando una prueba general, que cubra todos mis resultados a continuación:

1. Uno de cada tres números de Fibonacci es par.
2. 3 divide uno de cada cuatro números de Fibonacci.
3. 5 divide cada 5 números de Fibonacci.
4. El 4 divide uno de cada seis números de Fibonacci.
5. El 13 divide a uno de cada siete números de Fibonacci.
6. El 7 divide a uno de cada ocho números de Fibonacci.
7. El 17 divide uno de cada nueve números de Fibonacci.
8. El 11 divide cada 10 números de Fibonacci.
9. El 6, el 9, el 12 y el 16 dividen cada 12 números de Fibonacci.
10. El 29 divide cada 14º número de Fibonacci.
11. 10 y 61 divide cada 15º número de Fibonacci.
12. 15 divide cada 20 números de Fibonacci.

Answer 1

La mayoría de las propiedades de divisibilidad de los números de Fibonacci se derivan del hecho de que comprenden un secuencia de divisibilidad, es decir $\rm\,m\,|\,n\ \Rightarrow\ F_m\,|\,F_n.\,$ Todo de sus afirmaciones anteriores son casos especiales de esto, por ejemplo $\rm\,F_{15} = 610,\,$ así que $\rm\,15\,|\,n\ \Rightarrow\ F_{15}\,|\,F_n\,\Rightarrow\,610\,|\,F_n,\,$ que es precisamente su declaración $11,\,$ que $10$ y $61$ dividir cada $15\,$ El número de Fibonacci.

De hecho $\rm\,F_n\,$ es fuerte secuencia de divisibilidad, es decir $\rm\,(F_m,F_n) = F_{(m,n)},\,$ es decir $\rm\,gcd(F_m,F_n) = F_{\gcd(m,n)}.\,$ Este más fuerte se especializa en la propiedad anterior si $\rm\,m\mid n\,\ (\!\!\iff \gcd(m,n) = m\,\!).\,$ La prueba no es difícil. A continuación se presenta una forma sencilla de proceder. Recordemos el Ley de adición de Fibonacci $\rm\,F_{n+m} =F_{n+1}\,F_m + F_n\,F_{m-1}.\,$ Aplicar el turno $\rm\,n\to n-m\ $ esta ley de adición se convierte en $\rm\,F_n = F_{n-m+1}\,F_m + F_{n-m}\,F_{m-1}\!\equiv F_{n-m}\,F_{m-1}\pmod{F_m}.\,$ Así que para $\rm\,k=m-1\,$ podemos invocar el Teorema siguiente para concluir que $\rm\,f_n = F_n\,$ es una secuencia de divisibilidad fuerte.

Teorema $\ $ Dejemos que $\rm\ f_n\, $ sea una secuencia de números enteros tal que $\rm\ f_{\,0} =\, 0,\ f_1 = 1\ $ y tal que para todo $\rm\,n > m\,$ tiene $\rm\ \, \color{#c00}{f_n\equiv\, f_{\,k}\ f_{n-m}}\,\ (mod\ f_m)\ $ para algunos $\rm\,k < n,\ (k,m)\, =\, 1.\, $ Entonces $\rm\ (f_n,f_m)\, =\ f_{\,(n,\,m)} $

Prueba $\ $ Por inducción en $\rm\,n + m\,$ . El teorema es trivial si $\rm\ n = m\ $ o $\rm\ n = 0\ $ o $\rm\, m = 0.\,$ Supongamos que wlog $\rm\,n > m > 0.\,$ Desde $\rm\,k\!+\!m < n\!+\!m,\,$ por inducción $\rm\,(f_{\,k},f_m)=f_{\,(k,\,m)}\!=\,f_1 = 1.\,$ Así, $\rm\ (\color{#c00}{f_n},\,f_m)\, =\, (\color{#c00}{f_{\,k}\,f_{n-m}},\,f_m)\, =\, (f_{n-m},\,f_m)\, =\, f_{\,(n-m,\,m)} =\, f_{\,(n,\,m)} $ se deduce por inducción (que se aplica aquí ya que $\rm\,(n-m)+m\, <\, n+m\,\!),\,$ y empleando las conocidas leyes de gcd, a saber $\rm\,(a,b) = (a',\,b)\ \ if\ \ a\equiv a'\pmod{b}\ $ y $\rm\,(c\,a,b) = (a,b)\,$ si $\rm\,(c,b) = 1.\quad$ QED

Puede resultar útil examinar simultáneamente otras secuencias de divisibilidad fuerte, por ejemplo, ver mi publicar aquí en $\rm\,f_n = (x^n-1)/(x-1).\,$ En este caso $\rm\, \gcd(f_m,f_n)\, =\, f_{\,\gcd(m,n)}\,$ puede interpretarse como un $\rm\,q$ -análogo de la identidad entera de Bezout, por ejemplo $$\rm\displaystyle\ 3\ =\ (15,21)\ \ \leadsto\ \ \frac{x^3-1}{x-1}\ =\ (x^{15} + x^9 + 1)\ \frac{x^{15}-1}{x-1}\ -\ (x^9+x^3)\ \frac{x^{21}-1}{x-1}$$

Answer 2

Supongo que la forma estándar de entender todos estos resultados de divisibilidad en un solo golpe es observar que la secuencia de Fibonacci módulo de cualquier número N se convierte en periódico .

Por ejemplo, Fibonacci módulo 2 es 0, 1, 1, 0, 1, 1, 0, ...... demostrando la paridad de $F_n$ para $n=0,3,6,9,...$ .

Módulo de Fibonacci $3$ es 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 2, 0, ..... haciendo evidente que $3$ divide $F_n$ para $n=0, 4, 8, 12, ...$ .

¡Pruebe usted mismo las siguientes!

NOTA: la misma técnica se puede aplicar a cualquier secuencia recursiva lineal con coeficientes constantes.

Answer 3

Como ya han indicado otros carteles, para cada número entero positivo $N$ Hay un poco de $D(N)$ de manera que cada $D$ -a de Fibonacci es divisible por $N$ .

La siguiente pregunta lógica que se me ocurre es cómo calcular $D(N)$ . Obsérvese que, si $a$ y $b$ son relativamente primos, entonces $D(ab)=LCM(D(a), D(b))$ (gracias a hardmath por la corrección). En otras palabras, $D$ se determina por sus valores para las potencias primarias. Hablaré sólo de la computación $D(p)$ para $p$ un primo.

Recordemos la fórmula $$F_n = \frac{1}{\sqrt{5}} \left( \tau^n - (-\tau^{-1})^n \right)$$ donde $\tau = (1+\sqrt{5})/2$ .

Supongamos que el primo $p$ es $\pm 1 \bmod 5$ . Entonces hay una raíz cuadrada de $5$ en $\mathbb{Z}/p$ . La fórmula anterior sigue siendo válida en términos de esa raíz cuadrada. Por ejemplo, si $p=11$ entonces las raíces cuadradas de $5$ modulo $11$ son $4$ y $7$ . Tenemos $(1+4)/2 \equiv 8 \mod 11$ y $(1+7)/2 \equiv 4 \mod 11$ y, efectivamente, $F_n = (1/4) \left( 8^n - 4^n \right) \mod 11$ .

Así que $p$ divide $F_n$ si y sólo si $\tau^n = (- \tau^{-1})^n$ . En otras palabras, tenemos que calcular el orden de $- \tau^2$ en el grupo de unidades de $\mathbb{Z}/p$ . (En el ejemplo anterior, $- \tau^2 \equiv - 4^2 \equiv -64 \equiv 2 \mod 11$ Por lo tanto, la conclusión es que $11$ divide $F_n$ si y sólo si $2^n \equiv 1 \mod 11$ .) Por Teorema de Lagrange vemos que $D(p)$ dividirá $p-1$ para $p$ que es $\pm 1 \bmod 5$ .

Puedo decir más, pero este es realmente un proyecto excelente para que un teórico de números principiante juegue con él. ¿Qué se puede decir de los primos que son $\pm 2 \bmod 5$ ? ¿Qué se puede decir de los primeros poderes? Para $p \equiv \pm 1 \mod 5$ ¿Cuándo es que $D(p)$ dividir $(p-1)/2$ ? No hay una fórmula completa, pero hay muchas cosas buenas que observar.

Answer 4

La prueba general de esto es que los números de fibonacci surgen de la expresión $$F_n \sqrt{-5} = (\frac 12\sqrt{-5}+\frac 12\sqrt{-1})^n - (\frac 12\sqrt{-5}-\frac 12\sqrt{-1})^n$$

Dado que se trata de un ejemplo de la $a^n-b^n$ que $a^m-b^m$ divide, si $m \mid n$ se deduce que hay un único número, generalmente coprimo con el resto, para cada número. Algunos de los más pequeños serán $1$ .

La excepción es que si $f_n$ es este factor único, tal que $F_n = \prod_{m \mid n} f_n$ entonces $f_n$ y $f_{np^x}$ comparten un divisor común $p$ , si $p$ tampoco divide. Así, por ejemplo, $f_8=7$ y $f_{56}=7*14503$ comparten un divisor común de $7$ . Esto significa que el módulo sobre $49$ evidentemente también debe funcionar. Así que $f_{12} = 6$ comparte un divisor común con ambos $f_4=3$ y $f_3 = 4$ es única al conectarse con dos primos diferentes.

La ley de recriprocidad cuadrática de Gauss se aplica a los números de fibonacci, pero es un poco más compleja que para las bases regulares. En relación con la serie de fibonacci, reduce el módulo 20, a "superior" frente a "inferior" y "largo" frente a "corto". Para esta sección, 2 es como 7, y 5 como 1, módulo 20.

Los primos que se reducen a 3, 7, 13 y 17 son primos "superiores", lo que significa que su período divide $p+1$ . Los primos que terminan en 1, 9, 11, 19 son primos inferiores, lo que significa que sus períodos dividen $p-1$ .

Los primos de 1, 9, 13, 17 son "cortos", lo que significa que el periodo divide el máximo permitido, un número par de veces. Para 3, 7, 11, 19, divide el periodo un número impar de veces. Esto significa que todos los números de Fibonacci Impares pueden expresarse como la suma de dos cuadrados, como por ejemplo $233 = 8^2 + 13^2$ o en general $F_{2n+1} = F^2_n + F^2_{n+1}$

Así que una prima como $107$ que se reduce a $7$ tendría un período indicado que dividiría $108$ un número impar de veces. Su período real es $36$ . Una prima como $109$ divide $108$ un número par de veces, por lo que su período es un divisor de $54$ . Su período real es $27$ .

Una prima como $113$ se indica que es superior y corta, lo que significa que divide $114$ un número par de veces. En realidad tiene un periodo de $19$ .

La constante de Artin también se aplica aquí. Esto significa que estas reglas encuentran correctamente unas 3/4 partes de todos los períodos exactamente. El siguiente primo en esta progresión, $127$ , en realidad tiene el período indicado para un largo superior: 128. Lo mismo ocurre con $131$ (largo inferior), $137$ (cortocircuito superior, en el 69). Asimismo, $101$ (cortocircuito inferior) y $103$ (superior larga) muestran los períodos máximos indicados.

No hay primo bajo $20*120^4$ existe, donde si $p$ divide algunas $F_n$ También lo hace $p^2$ . Esto no excluye la existencia de dicho número.

Answer 5

Encontré que la respuesta de @David aquí es muy claro de entender, pero omitió algunos detalles menores. Reproduzco la respuesta de @David con todos los detalles. Todos los créditos son para @David.

---

Lemas:

$f_{s+t}=f_{s-1}f_t+f_sf_{t+1}$ (Presenté una prueba para este lema aquí )

$s\mid t\implies f_s\mid f_t$ (Un usuario presentó una prueba aquí )

Dejemos que $g=\gcd(m,n)$ y $d$ sea cualquier divisor común de $f_m,f_n$ . A partir de la definición de Máximo Común Divisor, está claro que $$\gcd(f_m, f_n) = f_{\gcd(n, m)}=f_g\iff\begin{cases} f_g\mid f_m\text{ and } f_g\mid f_n\\d\space\space\mid f_g\end{cases}$$

1. $f_g\mid f_m\text{ and } f_g\mid f_n$

A partir del segundo lema y del hecho de que $g=\gcd(m,n)$ tenemos $$g\mid m\Rightarrow f_g\mid f_m\quad\hbox{and}\quad g\mid n\Rightarrow f_g\mid f_n$$ .

2. $d\mid f_g$

Desde _La identidad de Bézout_ existe $x,y\in\mathbb Z$ tal que $g=mx+ny$ .

$f_m\mid f_{mx}$ y $d\mid f_m\implies d\mid f_{mx}$ . De la misma manera, $d\mid f_{ny}$ . Así, $d\mid f_{mx-1}f_{ny}+f_{mx}f_{ny+1}$ y a partir del segundo lema $d\mid f_{mx+ny}$ o, por el contrario $d\mid f_g$ .