Intereting Posts

Why maximum/minimum of linear programming occurs at a vertex?
A logic puzzle involving a balance.
Divide by a number without dividing.
Continuous Mapping Theorem for Random Variables
Evaluating $\frac{\sum_{k=0}^6 \csc^2(a+\frac{k\pi}{7})}{7\csc^2(7a)}$
Prove or disprove that the given expression is “always” positive
Equation for non-orthogonal projection of a point onto two vectors representing the isometric axis?
Fréchet differentiability from Gâteaux differentiability
what happens to rank of matrices when singular matrix multiply by non-singular matrix??
Every maximal ideal is principal. Is $R$ principal?
$\sqrt{c+\sqrt{c+\sqrt{c+\cdots}}}$, or the limit of the sequence $x_{n+1} = \sqrt{c+x_n}$
Does a finite ring's additive structure and the structure of its group of units determine its ring structure?
Famous uses of the inclusion-exclusion principle?
Proving inequality $\sqrt{\frac{2a}{b+c}}+\sqrt{\frac{2b}{c+a}}+\sqrt{\frac{2c}{a+b}} \leq \sqrt{3 \left(\frac{a}{b}+\frac{b}{c}+\frac{c}{a}\right)}$
Is the sequence $a_{n}=\prod\limits_{i=1}^{n}\left(1+\frac{i}{n^2}\right)$ decreasing?

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.

- Inverting the modular $J$ function
- The prime numbers do not satisfies Benford's law
- How was 78557 originally suspected to be a Sierpinski number?
- Number Theory: Solutions of $ax^2+by^2\equiv1 \pmod p$
- Percentage of Composite Odd Numbers Divisible by 3
- Algebraic independence over $\overline{\mathbb Q}$ and over $\mathbb Q$
- Prove that if $a\equiv b \pmod m $ , then $a \bmod m = b \bmod m$
- Find a solution: $3(x^2+y^2+z^2)=10(xy+yz+zx)$
- Lower bound for $\phi(n)$: Is $n/5 < \phi (n) < n$ for all $n > 1$?
- Number of solutions of $x^2_1+\dots+x^2_n=0,$ $x_i\in \Bbb{F}_q.$

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

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.

- Is there a different name for strongly Darboux functions?
- What is an intuitive explanation of the Hopf fibration and the twisted Hopf fibration?
- Tetrahedral Law of Cosines Proof
- What can we say about $f$ if $\int_0^1 f(x)p(x)dx=0$ for all polynomials $p$?
- Picking Multiples of 4
- Show that $\alpha$ $(G)$ $\le$ $\frac {|V(G)|}2$
- Isomorphism of Banach spaces implies isomorphism of duals?
- If $X \sim N(0,1)$, why is $E(X^2)=1$?
- How to find Laurent series Expansion
- Why is it important to have a discrepancy between image and codomain?
- Function that is both midpoint convex and concave
- Prove that a connected graph not having $P_4$ or $C_3$ as an induced subgraph is complete bipartite
- Direct sum of non-zero ideals over an integral domain
- Who is a Math Historian?
- Proof Verification for $n2^{n-1} = \sum\limits_{k=1}^n k\binom{n}{k}$