Computing a linear recurrence relation in modular arithmetic

Question

If we have a linear recurrence relation:

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

we can easily find an analytic formula for $F_i$ via the characteristic polynomial and initial conditions. However, how would one compute $F_i \mod m$? It is easy to see that $F_i \mod m$ must be periodic with period no larger than $m^k$, but I'm not sure it's even meaningful to solve the characteristic polynomial in the ring mod $m$.

Specifically, with $F_i$ defined as

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

it is asked to compute $F_{30000} \mod 31$ without the help of a calculator.

Is it possible to do without brute-forcing the sequence period by evaluating first $31^2$ terms by hand?

Answer 1

$F_n \equiv t^n \mod m$ is a solution if $t$ is a root of the characteristic polynomial mod $m$. In this case ($m = 31$, characteristic polynomial $p(x) = x^2 - x - 3$) the characteristic polynomial has no root in the field $\mathbb F_{31}$, so you go to an extension field where you get your two roots.

Alternatively, you might try computing some terms, and notice that $F_{8} \equiv F_{9} \equiv 12 \mod 31$. What does that tell you about $F_{8n}$?

Answer 2

Yes, the shift map sends the pair $(F_i, F_{i+1})$ to $(F_{i+1}, 3 F_{i+1} + F_i),$ so the corresponding matrix is

$$\begin{pmatrix}0 & 1\\ 3 & 1\end{pmatrix}.$$ Now, you need to raise this matrix to power $2999,$ and then apply it to the vector $\begin{pmatrix}1 \\ 1 \end{pmatrix}.$ You can raise the matrix to this how power by repeated squaring, which only takes about $20$ matrix multiplications, modulo $31.$