Computing the order of consecutive Fibonaccis, i.e. order of $f_n$ modulo $f_{n+1}$ I believe I must incorporate $f_n^2=f_{n-1}f_{n+1}+(-1)^{n+1}$ somehow.
 A: The accepted answer has many errors, so let's give a more careful proof.
First note we must have $\,n \ge 2,\,$ else $\,f_{n+1} = 1\,$ so order isn't defined $\!\bmod f_{n+1}$.

I believe I must incorporate $f_n^2= (-1)^{n+1}f_{n-1}f_{n+1}$ somehow.

Yes, that Cassini identity yields $\,f_n^2\equiv (-1)^{n+1}\pmod{\!f_{n+1}}$
Case $1\!:\ n$ even $\Rightarrow \color{#c00}{f_n^2 \equiv -1}.\,$ If $\,n=2\,$  then $\,f_2 = 1\,$ which has order $1$. Else $\,n\ge 4\,$ so $\,f_{n+1}\ge 3\,$ so $-1\not\equiv 1\pmod{\!f_{n+1}},\,$ so $\,f_n^2\not\equiv 1,\ f_n^4 \equiv (\color{#c00}{f_n^2})^2\!\equiv (\color{#c00}{-1})^2\!\equiv 1,\,$ so $\,f_n\,$ has order $4$ via Order Test.
Case $2\!:\ n$ odd $\Rightarrow f_n^2 \equiv 1\,$ so $\,{\rm ord}\,f_n = 2\,$ by $\,f_n\not\equiv 1,0\pmod{\!f_{n+1}}\,$ by $\,1\! <\! f_n \!<\! f_{n+1}$ for $\,n\ge 3$
In summary: $\,\ {\rm ord}\,f_n\:\!\pmod{\!f_{n+1}} \,=\, \begin{cases} 1\ \ {\rm if}\ \ n = 2\\ 4 \ \ {\rm if}\ \ n \,\text{ is even} \ge 4\\ 
2\ \ {\rm if}\  \,n\text{ is}\ \ \, {\rm odd}\, \ge 3\end{cases}$
A: Cassini's identity $f_n^2=f_{n-1}f_{n+1}+(-1)^{n+1}$ is indeed the key.
$f_n^2=f_{n-1}f_{n+1}+(-1)^{n+1}$ implies $f_n^2 \equiv (-1)^{n+1} \bmod f_{n+1}$. Thus

*

*$f_n^2 \equiv 1 \bmod f_{n+1}$ for $n$ odd


*$f_n^2 \equiv -1 \bmod f_{n+1}$ for $n$ even
Therefore,

*

*The order of $f_n^2$ mod $f_{n+1}$ is at most $2$ when $n$ is odd.


*The order of $f_n^2$ mod $f_{n+1}$ is $4$ when $n$ is even.
It remains to prove that $f_n \not\equiv 1 \bmod f_{n+1}$ when $n$ is odd. This is easy because $f_n \equiv -f_{n-1} \bmod f_{n+1}$.
In conclusion,

*

*The order of $f_n^2$ mod $f_{n+1}$ is $2$ when $n$ is odd.


*The order of $f_n^2$ mod $f_{n+1}$ is $4$ when $n$ is even.
