Basically I am curious if there's a direct way to calculate fibonacci(n) modulo m with a closed form formula so I don't have to bother with matrix exponentials.
Is there a closed form equation for fibonacci(n) modulo m?
3 Answers
This is not yet a complete solution; just a heuristical approach. I'm considering the cyclicity of residues modulo some m, here only for $m \in \mathbb P$ . After this we need only the sequences along one cycle.
I give a couple of empricial results, organized such that they shall give a hint how to proceed:
$ \small \begin{array} {lll} &m & \operatorname{fibcyclelength}(m) & \text{ general rule,estimated }\\ \hline \\ \hline \\ p=2& 2,4,8,16,32,... &3,6,12,24,48,...& a=(2+1),a_k=a \cdot 2^{k-1} \\ p=5& 5,25,125,625,...&20,100,500,... & a=5(5-1),a_k=a \cdot 5^{k-1}\\ \hline \\ p=\pm 2 \pmod 5 & 3,9,27,81,... &8,24,72,216,... &a=2(3+1),a_k=a \cdot 3^{k-1} \\ & 13,169,... &28,364,...&a=2(13+1),a_k=a \cdot 13^{k-1} \\ & 23,23^2 &48,&a=2(23+1), a_k=a \cdot 23^{k-1}\\ \hline \\ & 7,49,343 &16,112,...&a=2(7+1),a_k=a \cdot 7^{k-1} \\ & 17,289 &36,612,...&a=2(17+1),a_k=a \cdot 17^{k-1} \\ \hline \\ p= \pm 1 \pmod 5& 11,121, &10,110, & a=(11-1),a_k=a \cdot 11^{k-1} \\ & 31, &30,...&a=(31-1), a_k=a \cdot 31^{k-1} \\ \hline \\ & 19,... &18,...&a=(19-1), a_k=a \cdot 19^{k-1} \\ \end{array} $ I'm pretty confident that this is generalizable in the obvious way. Thus -if that above scheme is correct- we can compute the required results for that m without matrix-exponentiation after we have the entries over one cycle only..
Next step is then to look at the squarefree n with two primefactors, and their powers. Their sequences seem to begin with some irregularity, but finally seem to become regular in the above way. I've looked at n=6, n=10, n=15 so far, and if I get some idea of the characteristic of the irregularity I'll post it here.
I think this is old news, but it is straightforward to say what I know about this, in terms which I think there is some chance of addressing the intent of the question.
That is, as hinted-at by the question, the recursion $\pmatrix{F_{n+1}\cr F_n}=\pmatrix{1 & 1 \cr 1 & 0}\cdot \pmatrix{F_n\cr F_{n-1}}$ can be usefully dissected by thinking about eigenvectors and eigenvalues. Namely, the minimal (also characteristic) equation is $(x-1)x-1=0$, which has roots more-or-less the golden ratio. Thus, doing easy computations which I'm too lazy/tired to do on this day at this time, $F_n=A\cdot a^n + B\cdot b^n$ for some constants $a,b,A,B$. These constants are algebraic numbers, lying in the field extension of $\mathbb Q$ obtained by adjoining the "golden ratio"... This expression might seem not to make sense mod $m$, but, perhaps excepting $m$ divisible by $2$ or $5$, the finite field $\mathbb Z/p$ allows sense to be made of algebraic extensions, even with denominators dividing $2$ or $5$, the salient trouble-makers here.
So, except possibly for $m$ divisible by $2$ or $5$, the characteristic-zero formula for the $n$-th Fibonacci number makes sense.
The further question, raised in the other answer, of the precise period mod $m$ is probably as intractable (currently) as questions about primitive roots... Indeed. But, perhaps, the given question is not that hard...?
-
0Keep on truckin', bro... – 2012-11-20
Mod 19 there are two solutions to $x^2=x+1$, the generating function for Fibonacci numbers. These are $x=5, x=15$. On a whim (based on some of the above comments), I thought I would try these to get a closed form for fibonacci numbers mod 19. I tried $f(n) = \frac{15^n-5^n}{15-5},$ where the computation is to be done mod 19. And the formula worked, at least as far as I tried it.
(I'm just including this answer because it surprised me; perhaps the other responders above already know such a thing has to work.)
ADDED: The above seems to work fine for any prime for which $x^2=x+1$ has two solutions. I got that this is primes for which 5 is a quadratic residue. (it didn't work for $p=5$ since the only solution there is $x=3$ and then cannot imitate the above formula.)
Also I found that it seems to work even for $209 = 11 \cdot 19$, where there are four solutions, namely $15,81,129,195$; however one needs to choose a pair so that their difference is coprime to 209. Thus for mod 209 I tried the formula $f(n)=\frac{129^n-81^n}{129-81}$ and that seems to work to give fibonacci numbers mod 209.