Intereting Posts

The equivalence of “Every surjection has a right inverse” and the Axiom of Choice
Indefinite integral: $\int \frac{\mathrm dx}{\sqrt x(1+\sqrtx)}$
Show that $\sum_{n=0}^\infty r^n e^{i n \theta} = \frac{1- r\cos(\theta)+i r \sin(\theta)}{1+r^2-2r\cos(\theta)}$
Example of a not recursively enumerable set $A \subseteq \mathbb{N}$
How to prove $(c – b) ^ 2 + 3cb = x^3$ has no nonzero integer solutions?
S4/V4 isomorphic to S3 – Understanding Attached Tables
Units and Nilpotents
Why doesn't $\sum_{n=1}^\infty \frac{1}{n^{1+\frac{1}{n}}}$ converge?
Rellich-Kondrachov
Countable union of sets of cardinality $c$ has cardinality $c$
Straightedge-only construction of a perpendicular
How to win this game?
Calculating the fundamental group of $\mathbb R^3 \setminus A$, for $A$ a circle
Convex hexagon $ABCDEF$ following equalities $AD=BC+EF, BE=AF+CD, CF=DE+AB$. Prove that $\frac{AB}{DE}=\frac{CD}{AF}=\frac{EF}{BC}$
Find an abelian infinite group such that every proper subgroup is finite

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.

- $\tau$ and grouping of prime numbers
- Show $\mathrm{gcd}(7a+5,4a+3)=1$.
- Find the $44{th}$ digit of a $80$ digit number if number is divisible by $13$
- Prove that 1 less than the number of equivalence classes divides $p-1$ where $p$ is prime
- Who can prove that a triangular number cannot be a cube, fourth power or fifth power?
- Intuition and Stumbling blocks in proving the finiteness of WC group
- Use Fermat's little theorem to find remainder of powers
- I finally understand simple congruences. Now how to solve a quadratic congruence?
- If $n = a^2 + b^2 + c^2$ for positive integers $a$, $b$,$c$, show that there exist positive integers $x$, $y$, $z$ such that $n^2 = x^2 + y^2 + z^2$.
- Number of solutions to $x+y+z = n$

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.

- When is the $lcm$ of a fraction sum the actual denominator.
- Integral $ \int_{-\infty}^\infty \frac{e^{ikx}}{x^{3/2}}dx$
- A question about differentiation
- A criterion of flat modules
- Pi Estimation using Integers
- Small integral representation as $x^2-2y^2$ in Pell's equation
- Möbius strip and $\mathscr O(-1)$. Or $\mathscr O(1)$?
- why are subextensions of Galois extensions also Galois?
- Existence of a section of non-zero measure
- Limit related to $\zeta(x)$
- Evaluate: $\int_0^2 (\tan^{-1} (\pi x) -\ tan^{-1} x) \ \mathrm{d}x$
- For polynomial $f$, does $f$(rational) = rational$^2$ always imply that $f(x) = g(x)^2$?
- What is duality?
- Characteristic function of a product of random variables
- Questions about Combinatorial Proof of $\sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$