Primer número de Fibonacci con resto dado

Question

Me pregunto si existe un algoritmo más eficaz que la búsqueda por fuerza bruta para encontrar el primer número de Fibonacci con un resto determinado $r$ módulo de un número entero dado $m$ .

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...$$

Si $m=6$ y $r=0$ entonces $F_{12} = 144$ es el primer número de Fibonacci tal que $$~~F_{n} = 0 \pmod 6$$

Si $m=7$ y $r=3$ entonces $F_{4} = 3$ es el primer número de Fibonacci tal que $$~~F_{n} = 3 \pmod 7$$

También me pregunto cómo comprobar si dicho número de Fibonacci existe porque si $m=8$ y $r=4$ entonces ningún número de Fibonacci satisface la congruencia $~~F_{n} = 4 \pmod 8$

Gracias de antemano por cualquier idea.

Answer 1

No conozco un algoritmo más eficaz que la búsqueda por fuerza bruta, pero consideremos una pregunta como "¿hay algún número de Fibonacci con $F_n = 4 \pmod 8$ ". Si se escriben los números de Fibonacci módulo 8 se obtiene la secuencia

$1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, \ldots$

donde cada entrada es la suma de las dos anteriores, reducida a módulo 8. Una vez que $1, 1$ se repite la secuencia. Así que se puede ver de esto que $F_n = 4 \pmod 8$ y $F_n = 6 \pmod 8$ nunca ocurren. El punto aquí es que una vez que usted ve $1, 1$ de nuevo puede dejar de computar.