Cálculo de una relación de recurrencia lineal en aritmética modular

Question

Si tenemos una relación de recurrencia lineal:

$$F_{i+k} = c_0 F_{i} + c_1 F_{i+1} + \dots + c_{k-1} F_{i+k-1}$$

podemos encontrar fácilmente una fórmula analítica para $F_i$ mediante el polinomio característico y las condiciones iniciales. Sin embargo, ¿cómo calcular $F_i \mod m$ ? Es fácil ver que $F_i \mod m$ debe ser periódica con un período no superior a $m^k$ pero no estoy seguro de que tenga sentido resolver el polinomio característico en el anillo mod $m$ .

En concreto, con $F_i$ definido como

$$F_{i+2} = F_{i+1} + 3F_i$$ $$F_0 = F_1 = 1$$

se le pide que calcule $F_{30000} \mod 31$ sin ayuda de una calculadora.

¿Es posible prescindir del forzamiento bruto del período de secuencia evaluando primero $31^2$ términos a mano?

Answer 1

$F_n \equiv t^n \mod m$ es una solución si $t$ es una raíz del polinomio característico mod $m$ . En este caso ( $m = 31$ polinomio característico $p(x) = x^2 - x - 3$ ) el polinomio característico no tiene raíz en el campo $\mathbb F_{31}$ así que vas a un campo de extensión donde obtienes tus dos raíces.

También puede intentar calcular algunos términos y observar que $F_{8} \equiv F_{9} \equiv 12 \mod 31$ . ¿Qué le dice eso sobre $F_{8n}$ ?

Answer 2

Sí, el mapa de turnos envía el par $(F_i, F_{i+1})$ a $(F_{i+1}, 3 F_{i+1} + F_i),$ por lo que la matriz correspondiente es

$$\begin{pmatrix}0 & 1\\ 3 & 1\end{pmatrix}.$$ Ahora, necesitas elevar esta matriz a la potencia $2999,$ y luego aplicarlo al vector $\begin{pmatrix}1 \\ 1 \end{pmatrix}.$ Se puede elevar la matriz a esta potencia mediante repetidos elevamientos al cuadrado, lo que sólo lleva unos $20$ multiplicaciones de matrices, módulo $31.$