Los restos de los números de Fibonacci

Question

Dejemos que $a>b$ sean enteros positivos. ¿Existe un número de Fibonacci que sea $b$ modulo $a$ ?

Sabemos que los números de Fibonacci son periódicos módulo $a$ . En efecto, consideremos los pares $(F_i,F_{i+1})$ modulo $a$ . Sólo puede haber finitos (alrededor de $a^2$ ) tales pares. Así que algunos dos pares coinciden. Una vez que tenemos eso, también tenemos la periodicidad hacia atrás/adelante. Pero todavía no está claro para qué $a,b$ tendremos $F_i\equiv b\pmod a$ .

Answer 1

Hay infinidad de contraejemplos, y se pueden encontrar muchos como el siguiente. En primer lugar, para un número entero positivo $a$ , dejemos que $\kappa(a)$ denotan el período de los números de Fibonacci módulo $a$ . Es decir, es el menor número entero positivo tal que $F_{\kappa(a)+n}=F_n$ para todos $n$ . El número $\kappa(a)$ es conocido como el Período de Pisano o el Número de pared de $a$ . Como los valores de la secuencia de Fibonacci módulo $a$ repetir después $\kappa(a)$ sólo puede tener como máximo $\kappa(a)$ residuos módulo $a$ . Así que, mientras $\kappa(a) < a$ entonces debe existir $b < a$ tal que ningún número de Fibonacci sea igual a $b$ mod $a$ .

En realidad, podemos hacerlo un poco mejor ya que muchos de los residuos modulo $a$ se repetirá dentro de cada período. Lo tenemos,

• $F_1=F_2=1$ .
• $F_{\kappa(a)-n}\equiv (-1)^{n-1}F_n$ .

El primero de ellos reduce el número de clases de residuos de la secuencia de Fibonacci en 1, y el segundo lo reduce en el número de impar $n < \kappa(a)/2$ y hay $\lceil\kappa(a)/4-1/2\rceil$ posibles valores de $n$ . Además, mientras $\kappa(a) > 3$ estas relaciones son todas independientes, por lo que hay al menos \begin{align} a-\kappa(a)+1+\lceil\kappa(a)/4-1/2\rceil=\lceil a-3\kappa(a)/4+1/2\rceil&&{\rm(1)} \end{align} valores de $b < a$ tal que ningún número de Fibonacci sea igual a $b$ modulo $a$ . Tenga en cuenta también que $F_3=2\not\equiv0$ para cualquier $a > 2$ , por lo que tenemos $\kappa(a) > 3$ para todos $a > 2$ . Por lo tanto, existe al menos una $b < a$ tal que ningún número de Fibonacci sea igual a $b$ modulo $a$ siempre y cuando $\kappa(a) < (4a+2)/3$ .

Para calcular rápidamente los límites superiores de $\kappa(a)$ se pueden utilizar los siguientes hechos (resumidos en este documento de Elsenhans y Jahnel).

1. $\kappa(2)=3$ , $\kappa(5)=20$ .
2. Para la primera $p\equiv\pm1$ (mod 5), entonces $\kappa(p)\mid(p-1)$
3. Para los primos Impares $p\equiv\pm2$ (mod 5), entonces $\kappa(p)\mid2(p+1)$
4. Para el primer $p$ y $r\ge1$ entonces, $\kappa(p^r)\mid\kappa(p)p^{r-1}$ .
5. Si $a=a_1a_2\cdots a_N$ donde $a_i$ son coprimas entre sí, entonces $\kappa(a)$ divide el mínimo común múltiplo de $\kappa(a_1),\kappa(a_2),\ldots,\kappa(a_N)$ .

Sólo la segunda afirmación anterior es suficiente para generar infinitos ejemplos. Para cualquier primo $p\equiv\pm1$ (mod 5), tenemos $\kappa(p)\le p-1$ por lo que existe al menos $(p+5)/4$ valores de $b < p$ tal que ningún número de Fibonacci sea igual a $b$ mod $p$ . Por ejemplo, tomando $p=11$ un cálculo rápido muestra que este es el caso de $b=4,6,7,9$ . También podemos encontrar ejemplos utilizando el enunciado 5 anterior y multiplicando juntos comprime $a_i$ donde el $\kappa(a_i)$ tienen muchos factores comunes.

Answer 2

Utilicé el siguiente código lua para generar todos los valores posibles de a y b donde a > b hasta 100. Luego, muestra el resultado de b módulo a. Los resultados son ici (tenga en cuenta que en los resultados, el signo de porcentaje se utiliza como operador de módulo). A continuación se muestra el código que he utilizado para generarlo. (el .. es el operador de concatenación (une 2 trozos de texto))

strin=""
for a = 1, 100 do
    for b = 0 (a-1) do
        strin = strin .. "a=" .. a .. " b=" .. b .. "   b%a=" .. b%a .. "\010"
    end
end
print(strin)

Y, aquí está el código que utilicé para comprobar que a > b es siempre cierto para los números generados por el código en el parágrafo anterior (arriba). Aunque este código no utiliza ninguna variable externa, por lo que siempre mostrará la misma salida, puedes volver a comprobarlo si quieres utilizando este código. Sólo tienes que introducir el código en un compilador lua y si hay algún momento en el que a < b entonces te mostrará el valor de a y de b.

strin=""
for a = 1, 100 do
    for b = 0, (a-1) do
        if a > b then
            strin = strin .. "a=" .. a .. " b=" .. b .. "\010"
        end
    end
end
print(strin)

Entonces, queremos saber cuál es el número total de valores posibles para a y b cuando a o b no son más de 100. Así, he modificado un poco la codificación, y he encontrado que el total de valores posibles para a y b hasta 100 es $5050$ . El código que he utilizado para encontrarlo es el siguiente.

num = 0
for a=1, 100, 1 do
    for b = 0, (a-1), 1 do
        num = num + 1
    end
end
print(num)

A continuación, para comprobar los números de Fibonacci. Todos los números de Fibonacci ( no la secuencia de Fibonacci ) menores o iguales a 100 son: 0, 1, 2, 3, 5, 8, 13, 21, 34, 55 y 89. Por lo tanto, he creado un programa lua para averiguar qué b módulo a son Fibonacci. Los resultados son ici . La cantidad total de números Fibonacci encontrados es de 986 ( $19.\overline{5247}$ de los números totales probados ). El siguiente es el código que he utilizado.

fibs = {0;1;1;2;3;5;8;13;21;34;55;89}
strin=""
for a = 1, 100, 1 do
    for b = 0, (a-1), 1 do
        for k, v in pairs(fibs) do
            if b % a == v then
                strin = strin .. "a=" .. a .."  b=" .. b .. "   b%a=" .. b%a .. "\010"
            end
        end
    end
end
print(strin)

En general, sí, porque hay toneladas de números de Fibonacci que son b módulo a ( e incluso a módulo b ) sólo en los primeros 100 valores de los números a y b.

En un tema relacionado, acabo de cambiarlo un poco para ver un módulo b hasta 100 donde a > b. El resultado es ici . El siguiente es el código que he utilizado.

local strin=""
for a=1, 100, 1 do
    for b = 0, (a-1), 1 do
        strin = strin .. "a=" .. a .. " b=" .. b .. "   a%b=" .. a%b .. "\010"
    end
end
print(strin)

Luego, sacar los números de Fibonacci fue otro simple programa. Los resultados se pueden encontrar ici . El total de partidos es de 2399 ( casi la mitad - $ 47.\overline{5049} $ % ). El siguiente es el código que he utilizado para generarlo.

fibs = {0;1;1;2;3;5;8;13;21;34;55;89}
strin = ""
for a=1, 100, 1 do
    for b = 0, (a-1), 1 do
        for k, v in pairs(fibs) do
            if a%b==v then
                strin = strin .. "a=" .. a .. " b=" .. b .. "   a%b=" .. a%b .. "\010"
            end
        end
    end
end
print(strin)