¿Forman los números de Fibonacci un sistema completo de residuos en cada módulo?

Question

Quiero demostrarlo: $$\forall x,m\ \exists n:x\equiv_mF_n$$

Supongo que se puede demostrar esto por el principio de encasillamiento, pero no he conseguido encontrar una serie de $m+1$ números que cada uno quiere ocupar un número diferente.

Answer 1

No, porque:

Si $m=11$ entonces los números de Fibonacci son $\pmod {11}$

$$ 0,1,1,2,3,5,8,2,10,1,0,1,1,\dots $$

así que $x = 4,6,7,9$ nunca se alcanzan.

Answer 2

Esto no es cierto módulo 8, un cálculo muestra que ningún número de Fibonacci es equivalente a $ 4$ o $6 \mod 8$ .

---

De hecho, se puede utilizar el principio de encasillamiento para demostrar que esto nunca es cierto módulo a prime módulo $m$ que satisface $m\equiv 1$ o $4\mod 5$ es decir, siempre hay algún residuo $a$ tal que $$ a \not\equiv F_n \mod m \quad\text{for any }n.$$

Pista: Recuerda la ecuación de forma cerrada para los números de Fibonacci $$ F_n = A\phi^n + B\bar{\phi}^n \quad$$ donde $\phi = \frac12(1+\sqrt{5})$ es la proporción áurea y $\bar{\phi} = \frac12(1 -\sqrt{5})$ es su conjugado de Galois, y $A$ y $B$ son constantes que no son importantes en este momento.

---

Prueba: Si el primo $m$ satisface la condición de congruencia anterior módulo $5$ entonces por reciprocidad cuadrática los números $\pm\sqrt{5}$ están en el campo finito $\mathbb F_m$ y por lo tanto $\phi, \bar \phi \in \mathbb F_m$ . Dado que el grupo multiplicativo módulo $m$ tiene orden $\#\mathbb F_m^\times = m-1$ , la expresión de forma cerrada anterior implica que modulo $m$ los números de Fibonnaci son periódicos con periodo (dividiendo) $m-1$ . Por lo tanto, puede haber como máximo $m-1$ residuos disticos que aparecen en $\{F_n \mod m\}_n$ .

Por otro lado, si $m \equiv 2,3$ modulo $5$ (y $m \neq 5$ ), los números $\phi, \bar\phi$ se encuentran en la extensión cuadrática $\mathbb F_{m^2}$ y los números de Fibonacci $\{F_n \mod m\}_n$ tener el periodo $m^2 - 1$ . Así que el principio de encasillamiento no ayuda en este caso.

Answer 3

La secuencia de Fibonacci módulo $n$ es periódica, porque un par de números consecutivos se repetirá necesariamente después de un máximo de $n^2$ pasos.

Si $p>5$ es primo y $5$ es un residuo cuadrático módulo $p$ , lo que significa que $5$ es un cuadrado módulo $p$ Entonces, trabajando en el $p$ -campo de elementos, la ecuación característica de la recurrencia $a_{n+2}-a_{n+1}-a_n=0$ tiene raíces $$ r_+=\frac{1+u}{2}\qquad r_-=\frac{1-u}{2} $$ donde $u^2=5$ por lo que el término general tiene la forma $$ \alpha r_+^n+\beta r_-^n $$ Como queremos $a_0=0$ y $a_1=1$ necesitamos \begin{cases} \alpha+\beta=0\\ \alpha r_+ +\beta r_-=1 \end{cases} es decir, $\beta=-\alpha$ y $\alpha=1/u$ . Por lo tanto, $$ a_n=\frac{1}{u}(r_+^n-r_-^n) $$ Ya que por el pequeño Fermat tenemos $s^p=s$ por cada $s$ el período es como máximo $p-1$ y $1$ aparece dos veces en el período, por lo que no pueden aparecer al menos dos restos.

Answer 4

Valores con un sistema de residuos completo $\{0, 1, \dots, n-1 \}$ son números cualesquiera de la forma $$5^k, 2 \cdot 5^k, 4 \cdot 5^k, 3^j 5^k, 6 \cdot 5^k, 7 \cdot 5^k, 14 \cdot 5^k$$

con $k \ge 0, j \ge 1$ .

Fuentes (de A079002 ):

• S. A. Burr, Sobre los módulos para los que los números de Fibonacci contienen un sistema completo de residuos , Fibonacci Quarterly, 9 (1971), 497-504.
• Cheng Lien Lang y Mong Lung Lang, El sistema Fibonacci y la integridad de los residuos , arXiv:1304.2892 [math.NT], 2013.