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 for $n=2^i5^j$, $i,j\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 $\rho_g(n)$ divides $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$.

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.

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 for $n=2^i5^j$. 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 $\rho_g(n)$ divides $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 satisfy $\rho(p^k)/2 \leq p^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)= & lcm\{\rho(p_i^{k_i}) \mid i=0,\dots r\}= 2lcm\{\frac{\rho(p_i^{k_i})}{2} \mid i=0,\dots r\} \\ & \leq 2\prod_{i=0}^r \frac{\rho(p_i^{k_i})}{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$.

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 for $n=2^i5^j$, $i,j\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 $\rho_g(n)$ divides $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$.