The question above is about lower bounds, but I allow myself to comment about upper bounds:
$\pi(n)$, the period function of the Fibonacci sequence mod $n$, satisfies $\pi(n)\leq 6n$ and equality holds iff $n=2\cdot 5^k$ for some $k\geq 1$.
This fact is well known. In the 90's it was considered here as a puzzle to the monthly readers. $\pi(n)$ was also discussed in an elementary fashion in the 60's in this monthly paper.

But really, I want to share a little observation which forms a generalization of the above mentioned fact:
denoting, for an element $g\in \mathrm{GL}_2(\mathbb{Z})$, by $\rho_g(n)$ the order of the image of $g$ in $\mathrm{GL}_2(\mathbb{Z}/n)$, $\rho_g(n)\leq 6n$. This is a generalization because $\rho_g(n)=\pi(n)$ for
$g= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$.
Note that if $\det(g)=-1$ then $\rho_g(n)=2\rho_{g^2}(n)$, thus it is enough to prove
that for $g\in \mathrm{SL}_2(\mathbb{Z})$, $\rho_g(n)\leq 3n$.
Let me now fix $g\in \mathrm{SL}_2(\mathbb{Z})$, denote $\rho(n)=\rho_g(n)$
and prove that indeed $\rho(n)\leq 3n$.

First note that, for natural $p$ and $n$, if $p$ divides $n$ then $\rho(pn)$ divides $p\rho(n)$.
This follows by expanding the right hand side of
$ g^{p\rho(n)}=(g^{\rho(n)})^p=(1+nh)^p$
and note that it is 1 mod $pn$.
By induction we conclude that for every $k>1$, $\rho(p^k)$ divides $p^{k-1}\rho(p)$.

Assume now $p$ is a prime and note that $\rho(p)$ divides either $p-1,p+1$ or $2p$.
Indeed, if $\bar{g}\in \mathrm{SL}_2(\mathbb{F}_p)$ is diagonalizable over $\mathbb{F}_p$
then its eigenvalues are in $\mathbb{F}_p^\times$ and their orders divides $p-1$,
else, if $\bar{g}$ is diagonalizable over $\mathbb{F}_{p^2}$ then
its eighenvalues $\alpha,\beta$ are conjugated by the Frobenius automorphism, thus
their order divides $p+1$ because
$\alpha^{p+1}=\alpha\alpha^p=\alpha\beta=\det(\bar{g})=1$,
else $\bar{g}$ has a unique eigenvalue, which must be a $\pm 1$ by $\det(\bar{g})=1$, thus
$\bar{g}^2$ is unipotent and its order divides $p$.
For $p=2$, in the last case, there was no reason to pass to $g^2$,
as $-1=1$ in $\mathbb{F}_2$, thus $\rho(2)$ is either 1,2 or 3.

From the above two points, we conclude that for every odd prime $p$ and natural $k$, $\rho(p^k)$ divides $p^{k-1}(p-1)$, $p^{k-1}(p+1)$ or $2p^k$.
All these numbers are even and bounded by $2p^k$,
thus $\mathrm{lcm}\{\rho(p^k),2\} \leq 2p^k$.
For $p=2$ we get that $\rho(2^k) \leq 2^{k-1}\cdot 3$.

Fix now an arbitrary natural $n$.
Write $n=2^km$ for an odd $m$ and decompose $m=\prod_{i=0}^r p_i^{k_i}$. Then
\begin{align*}
\rho(m)= \mathrm{lcm}\{\rho(p_i^{k_i}) \mid i=0,\dots r\}
\leq \mathrm{lcm}\{\mathrm{lcm}\{\rho(p_i^{k_i}),2\} \mid i=0,\dots r\} =\\
2\mathrm{lcm}\{\frac{\mathrm{lcm}\{\rho(p_i^{k_i}),2\}}{2} \mid i=0,\dots r\} \leq 2\prod_{i=0}^r \frac{\mathrm{lcm}\{\rho(p_i^{k_i}),2\}}{2}\leq 2\prod_{i=0}^r p_i^{k_i} =2m
\end{align*}
and we get
$$ \rho(n) = \rho(2^km) \leq \rho(2^k) \cdot \rho(m) \leq 2^{k-1}\cdot 3 \cdot 2m = 3\cdot 2^km=3n. $$

This finishes the proof that $\rho(n)\leq 3n$.

As always, it is interesting to analyze the case of equality.
For $g\in \mathrm{SL}_2(\mathbb{Z})$ we have $\rho_g(n)=3n$ for some $n$
iff $\mathrm{tr}(g)$ is odd and not equal $-1$ or $-3$.
If $g$ satisfies this condition, then $n$ satisfices $\rho_g(n)=3n$ iff $n=2st$, for some odd $s\geq 3$, $t\geq 1$ where
every prime factor of $s$ divides $\mathrm{tr}(g)+2$,
every prime factor of $t$ divides $\mathrm{tr}(g)-2$ and $g$ is not $\pm 1$
modulo any of these prime factors.

For $g$ satisfying $\det(g)=-1$, using the identity $\mathrm{tr}(g^2)=\mathrm{tr}(g)^2-2\det(g)$, we get that $\rho_g(n)=6n$ for some $n$
iff $\mathrm{tr}(g)$ is odd and in this case,
$n$ satisfices $\rho_g(n)=6n$ iff $n=2st$, for some odd $s\geq 3$, $t\geq 1$ where
every prime factor of $s$ divides $\mathrm{tr}(g)+4$,
every prime factor of $t$ divides $\mathrm{tr}(g)$ and $g$ is not $\pm 1$
modulo any of these prime factors.

Specifically for $g=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$,
$\det(g)=-1$, $\mathrm{tr}(g)=1$ is odd, 5 is the only prime factor of $\mathrm{tr}(g)+4$ and there is no prime factor for $\mathrm{tr}(g)$.
Since $g$ is not $\pm 1$
modulo 5, we get that $\pi(n)=\rho_g(n)=6n$
iff $n=2\cdot 5^k$ for some $k\geq 1$, as claimed above.

and$F_{k+1} \equiv 1 \bmod p$. The first congruence need not imply the second. For example, take $p = 61$. The smallest $k \geq 1$ such that $F_k \equiv 0 \bmod 61$ is $k = 15$, but $F_{16} \equiv 11 \not\equiv 1 \bmod 61$, so the Fibonacci sequence mod $61$ does not have period $15$. The period of $\{F_n \bmod 61\}$ is $60$. $\endgroup$1more comment