Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 0 down vote accepted

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.

share|improve this answer
add comment

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...?

share|improve this answer
    
Keep on truckin', bro... –  TonyK Nov 20 '12 at 20:10
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.