Cada primer distribuir un número Fibonacci?

Question

Estoy tring para mostrar que $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$ donde $F$ es la secuencia de fibonacci se define como $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. ¿Cómo puedo hacer esto?

Originalmente, estaba tratando de mostrar que $\forall a\in\Bbb N\;\exists n\in\Bbb N:a|F_n$. Pronto me enteré de que si el $k$-th Fibonacci puede ser dividido por $m$, $nk$- ésimo de Fibonacci también puede ser dividido por $m$, y esto puede ser reducido a mi problema original de este post.

Answer 1

Sí. Considere la posibilidad de cualquier prime $p$. (En realidad no necesitamos $p$ a ser el primer; considerar cualquier número distinto de cero $p$.)

Usted puede tomar $F_0 = 0$ que es divisible por $p$, pero vamos a suponer que usted quiere algunos $n > 1$ tal que $F_n$ es divisible por $p$. Considerar la secuencia de Fibonacci modulo $p$; llamarlo $F'$.

Es decir, usted tiene $F'_0 = 0$, $F'_1 = 1$, y para $n \ge 0$, usted tiene $F'_{n+2} \equiv F'_{n+1} + F'_n \mod p$.

Ahora, sólo hay $p^2$ posibles pares de restos de $(F'_k, F'_{k+1})$, por lo que algunos par consecutivo de los restos debe producirse de nuevo en algún momento. Además, el futuro de la secuencia está totalmente determinado por su valor en unos dos días consecutivos de los índices, de manera que la secuencia debe repetir después de ese punto. Y no puede entrar en un ciclo que no incluye a $(F'_0, F'_1)$, porque también podemos trabajar la secuencia al revés: podemos encontrar $F'_{k-1}$$F'_{k-1} \equiv F'_{k+1} - F'_{k} \mod p$, etc.

Esto significa que siempre existe algo de $n > 0$ tal que $F'_n \equiv F_0 \equiv 0 \mod p$$F'_{n+1} \equiv F_1 \equiv 1 \mod p$. Tal $n$ va a hacer. Este es el llamado período de la secuencia modulo $p$ (o $p$th Pisano período; por supuesto, algunos más pequeños $n$ también puede existir (para que $F'_{n+1} \not\equiv 1 \mod p$).

Answer 2

Según el artículo de Wikipedia sobre los números de Fibonacci si $p$ es un número primo entonces

$$F_{p - \left(\frac{p}{5}\right)} \equiv 0 \text{ (mod } p) $$

donde $\left(\frac{p}{5}\right)$ es el símbolo de Legendre.

$$\left(\frac{p}{5}\right) = \begin{cases} 0 & \textrm{if}\;p =5\\ 1 &\textrm{if}\;p \equiv \pm1 \pmod 5\\ -1 &\textrm{if}\;p \equiv \pm2 \pmod 5.\end{cases}$$

Por ejemplo, si $p = 31$$F_{30} = 832040 = 2^3 \times 5 \times 11 \times 31 \times 61$.

La referencia es Lemmermeyer (2000), pp 73-4.

Answer 3

Podemos, de hecho, muestran una declaración más fuerte con algo de la teoría algebraica de números: Si $p>5$ es primo, a continuación, $p|F_{p\pm 1}$ para algunos la elección de $+$ o $-$.

Supongamos $\left(\frac{5}{p}\right)=1$. En este caso, $p$ se divide en $\mathbf{Z}\left[\frac{1+\sqrt{5}}{2}\right]=\mathbf{Z}[\varphi]$. Así, podemos escribir la $p=\pm\pi\bar\pi$ donde $\pi$ $\bar\pi$ son conjugadas de los números primos en $\mathbf{Z}[\varphi]$ que no difieren en una unidad. Escribir $\pi=x+y\varphi$, lo $x+y\varphi\equiv 0\pmod{\pi}$. Ahora, si $p|y$,$\pi|y,x$, contradicción, por lo $p\nmid y$. Por lo tanto, $y$ tiene una inversa modulo $p$, decir $y'$. Luego tenemos a $\pi|p|yy'-1$, lo $\varphi\equiv -xy'\pmod{\pi}$. Resumiendo, $\varphi\equiv k\pmod{\pi}$ para algunos entero $k\not\equiv 0\pmod{p}$. Por FLT, $k^{p-1}\equiv 1\pmod{p}$, lo $\varphi^{p-1}\equiv k^{p-1}\pmod{\pi}$. Por lo tanto $\varphi^{p-1}\equiv 1\pmod{\pi}$. Del mismo modo, podemos ver que $\bar\varphi^{p-1}\equiv 1\pmod{\pi}$, lo $F_{p-1}\sqrt{5}\equiv 0\pmod{\pi}$. Desde $p$ $5$ son necesariamente relativamente primos, $\pi|F_{p-1}$, e $\bar\pi|F_{p-1}$. Por lo tanto $\pi\bar\pi = p|F_{p-1}$ en este caso.

Ahora, supongamos $\left(\frac{5}{p}\right)=-1$. Tenemos $5^{(p-1)/2}\equiv -1\pmod{p}$, por el Criterio de Euler. Ahora, aplicando el Binomio-el teorema de Binet la fórmula de los rendimientos de los varios términos que contengan $\binom{p+1}{k}\equiv 0\pmod{p}$. Después de reducir el modulo $p$ nos quedará $\dfrac{\sqrt{5}^{p+1}+1}{2^t}$ algunos $t$, que también es divisible por $p$ (trabajando en $\mathbf{Z}[\varphi]$), por lo $p|F_{p+1}$ en este caso.

Nota: Esta es una prueba de que el post anterior por 01000100, que afirma que $p|F_{p-\left(\frac{p}{5}\right)}$

Answer 4

La respuesta es trivial: si $F_0=0$ es un múltiplo de cualquier prime (o natural). Pero esto puede ser extendido para responder a su pregunta real: ¿esto también suceda (por determinado$~p$) para algunos $F_n$$n>0$.

De hecho, el primer coeficiente (el de $F_{n-2}$,$1$) de la de Fibonacci, la recurrencia es obviamente invertible modulo cualquier prime$~p$, lo que significa que la recurrencia se puede correr hacia atrás modulo$~p$: conocer las clases de $F_{n-1}$ e de $F_n$ se puede recuperar la clase de$~F_{n-2}$ únicamente. Esto significa que en el conjunto de $\Bbb F_p^2$ de los pares de clases de términos sucesivos, la de Fibonacci de la recurrencia se define un bijection (una permutación de todos los pares). A continuación, ya que el conjunto de pares es finito, algún poder de esta operación debe ser la identidad. Esto implica que en el caso de $F_n\equiv0\pmod p$ que pasa por $n=0$ repite para algunos $n>0$.

Answer 5

De cualquier forma lineal recursiva entero secuencia tiene la propiedad de que cada una lo suficientemente grande como primer divide algunas plazo, siempre y cuando

algunas término de la secuencia es igual a $0$.

Que se desprende de la solución de lineal recursiva secuencias. Número de la secuencia, de modo que $S_0 = 0$, y considerar los números primos $p$ no dividir cualquiera de los denominadores o característica de las raíces que aparecen en la solución algebraica de la recurrencia (esto es todo, pero un número finito de números primos). Si $k$ es elegido de manera que $\alpha^k=1 \mod p$ para todas las raíces $\alpha$ del polinomio característico, a continuación, $p|S_k$ si las raíces son distintas, y $p|S_{kp}$ si o no las raíces son distintas.

Si la secuencia tiene la propiedad adicional de que

la recursividad se puede correr hacia atrás (su extrema coeficientes se $\pm 1$)

a continuación, cada primer divide algunas término de la secuencia.

La segunda declaración es lo que se demostró en las otras respuestas: cuando se reduce mod $p$, una recursividad que se puede ejecutar en ambas direcciones es periódica y así se repite el valor de $0$.

A la inversa, el que debe existir un término igual a $0$ con el fin de tener un término igual a $0$ mod $p$ para todos los gran $p$, es plausible pero parece difícil de probar.