I stumbled upon these very nice looking notes by Brian Lawrence on the period of the Fibonacci numbers over finite fields. In them, he shows that the period of the Fibonacci sequence over $\mathbb{F}_p$ divides $p$ or $p-1$ or $p+1$.
I am wondering if there are explicit lower bounds on this period. Is it true, for instance, that as $p \to \infty$, so does the order?
A quick calculation on my computer shows that there are some "large" primes with period under 100.
9901 66
19489 58
28657 92
This maybe too elementary for this site, so if your question is closed, you might try asking on MathStackExchange. Many questions about the period can be answered by using the formula $$ F_n = (A^n-B^n)/(A-B), $$ where $A$ and $B$ are the roots of $T^2-T-1$. So if $\sqrt5$ is in your finite field, then so are $A$ and $B$, and since $AB=-1$, the period divides $p-1$ from Fermat's little theorem. If not, then you're in the subgroup of $\mathbb F_{p^2}$ consisting of elements of norm $\pm1$, so the period divides $2(p+1)$. If you want small period, then take primes that divide $A^n-1$, or really its norm, so take primes dividing $(A^n-1)(B^n-1)$, where $A$ and $B$ are $\frac12(1\pm\sqrt5)$. An open question is in the other direction: Are there infinitely many $p\equiv\pm1\pmod5$ such that the period is maximal, i.e., equal to $p-1$?
BTW, the source you quote isn't quite correct, if $p\equiv\pm2\pmod5$, then the period divides $2(p+1)$, but might not divide $p+1$. The simplest example is $p=3$, where the Fibonacci sequence is $$ 0,1,1,2,0,2,2,1,\quad 0,1,1,2,0,2,2,1,\ldots. $$ Note that the first 0 does not necessarily mean that it will start to repeat. What happens is that the term before the first $0$ is $p-1$, so the first part of the sequence repeats with negative signs before you get to a consecutive $0$ and $1$.
I won't address your question about how small the period of $\{F_n \bmod p\}$ can be as $p$ grows, but instead ask if the upper bounds on the period can be achieved infinitely often. For consistency I'll use the notation from Joe Silverman's answer: set $A = (1 + \sqrt{5})/2$ and $B = (1-\sqrt{5})/2$, so $F_n = (A^n - B^n)/(A-B) = (A^n - B^n)/\sqrt{5}$. Note $A+B = 1$, $A - B = \sqrt{5}$, and $AB = -1$.
Claim: For a prime $p \not= 2$ or $5$, the period of the Fibonacci sequence $\{F_n \bmod p\}$ is the smallest even positive integer $k$ such that $A^k = 1$ in characteristic $p$.
This claim involves working in the field $\mathbf F_p(\sqrt{5})$, where $\sqrt{5}$ is a square root of 5 in characteristic $p$, so we can regard $A = (1+\sqrt{5})/2$ as a number in the field $\mathbf F_p(\sqrt{5})$, which is either $\mathbf F_p$ or $\mathbf F_{p^2}$. (The notation $\mathbf F_p$ and $\mathbf F_{p^2}$ are fields of order $p$ and $p^2$, not having anything to do with the "$F$" in Fibonacci number notation.) The claim is saying that $F_{n+k} \equiv F_n \bmod p$ for all $n \geq 0$ (or just all sufficiently large $n \geq 0$) if and only if $A^k = 1$ in $\mathbf F_p(\sqrt{5})$ for even $k$, so the period of $\{F_n \bmod p\}$ is the smallest even $k \geq 1$ such that $A^k = 1$ in $\mathbf F_p(\sqrt{5})$.
Proof. View the congruence $F_{n+k} \equiv F_n \bmod p$ as an equation $F_{n+k} = F_n$ in the subfield $\mathbf F_p$ of $\mathbf F_p(\sqrt{5})$. The Fibonacci formula $F_n = (A^n - B^n)/\sqrt{5}$ in $\mathbf R$ is also a valid formula in fields of characteristic $p$ when we view $\sqrt{5}$ in characteristic $p$ and set $A = (1+\sqrt{5})/2$ and $B = (1-\sqrt{5})/2 = 1-A$ in characteristic $p$. In $\mathbf F_p(\sqrt{5})$, \begin{align*} F_{n+k} = F_n & \Longleftrightarrow \frac{A^{n+k}-B^{n+k}}{\sqrt{5}} = \frac{A^n-B^n}{\sqrt{5}} \\ & \Longleftrightarrow A^n(A^k-1) = B^n(B^k-1). \end{align*} In a field of characteristic $p \not= 2$ or $5$, $A$ and $B$ are nonzero since $AB = -1$. Suppose in $\mathbf F_p(\sqrt{5})$ that $A^k \not= 1$. Then in this field, $$ F_{n+k} = F_n \Longrightarrow (A/B)^n = (B^k-1)/(A^k-1). $$ The ratio $A/B$ in characteristic $p$ is not $1$ since $A = B \Longrightarrow 5 = 0$ in characteristic $p$, which is false since $p \not= 5$. Therefore $(A/B)^n$ is not constant as $n$ varies, but $(B^k-1)/(A^k-1)$ is constant as $n$ varies. Thus $A^k = 1$ in $\mathbf F_p(\sqrt{5})$, so $B^n(B^k-1) = A^n(A^k-1) = 0$, so $B^k = 1$ (we never have $B^n = 0$ in characteristic $p$). Since $B^k = (-1/A)^k = (-1)^k/A^k$, we have $A^k = 1$ and $B^k = 1$ if and only if $A^k = 1$ and $(-1)^k = 1$. Since $-1 \not= 1$ in characteristic $p$ when $p \not= 2$, we have $A^k = 1$ and $(-1)^k = 1$ in $\mathbf F_p(\sqrt{5})$ if and only if $A^k = 1$ in characteristic $p$ and $k$ is even.
That completes the proof of the claim.
Since $B = -1/A$, if $A$ in characteristic $p$ has odd order $m$ then $B$ in characteristic $p$ has order $2m$. Therefore the claim says the period of $\{F_n \bmod p\}$ is the least $k \geq 1$ such that $A^k = 1$ and $B^k = 1$ in characteristic $p$: that $k$ is necessarily even.
For $p \not= 2$ or 5, the field $\mathbf F_p(\sqrt{5})$ has order $p$ or $p^2$ depending on whether or not $5 \bmod p$ is a square: its order is $p$ when $p \equiv \pm 1 \bmod 5$ and its order is $p^2$ when $p \equiv \pm 2 \bmod 5$. Therefore the group of nonzero elements $\mathbf F_p(\sqrt{5})^\times$ has order $p-1$ if $p \equiv \pm 1 \bmod 5$ and order $p^2-1$ if $p \equiv \pm 2 \bmod 5$. Since $p-1$ and $p^2-1$ are both even, the period of $\{F_n \bmod p\}$ divides $p-1$ if $p \equiv \pm 1 \bmod 5$ and it divides $p^2-1$ if $p \equiv \pm 2 \bmod 5$. As Joe points out in his answer, when $p \equiv \pm 2 \bmod 5$ the period of $\{F_n \bmod p\}$ divides $2(p+1)$, which is a proper factor of $p^2-1$.
This situation is reminiscent of Artin's primitive root conjecture, which says that for $a \in \mathbf Z$ that is not $\pm 1$ or a perfect square, there are infinitely many primes $p$ such that $a \bmod p$ has order $p-1$ in $\mathbf F_p^\times$, and in fact there is a positive density of such primes. This conjecture is known to be a consequence of the Generalized Riemann Hypothesis (GRH). This conjecture and its connection to GRH can be extended to number fields, and to talk about the multiplicative order of $A$ in characteristic $p$ amounts to looking at an analogue of Artin's primitive root conjecture with $\mathbf Z$ replaced by $\mathbf Z[A]$, which is the ring of integers of $\mathbf Q(\sqrt{5})$. This is discussed in Barendrecht's 2018 bachelor's thesis here. For example, GRH implies that the set of (nonzero) prime ideals $\mathfrak p$ in $\mathbf Z[A]$ such that $A \bmod \mathfrak p$ generates all of $(\mathbf Z[A]/\mathfrak p)^\times$ has a positive density using the last result of the thesis, Corollary 3.1.2, and therefore there are infinitely many such prime ideals $\mathfrak p$ in $\mathbf Z[A]$.
Every nonzero prime ideal $\mathfrak p$ in $\mathbf Z[A]$ is a factor of $(p) = p\mathbf Z[A]$ for some prime number $p$: if $p \equiv \pm 1 \bmod 5$ then $(p) = \mathfrak p\mathfrak p'$ for two prime ideals $\mathfrak p$ and $\mathfrak p'$, and $\mathbf Z[A]/\mathfrak p$ and $\mathbf Z[A]/\mathfrak p'$ are fields of order $p$. If $p \equiv \pm 2 \bmod 5$, then $(p) = \mathfrak p$ is a prime ideal in $\mathbf Z[A]$ and $\mathbf Z[A]/(p)$ is a field of order $p^2$. When $p \equiv \pm 2 \bmod 5$, the multiplicative order of $A$ in characteristic $p$ is a factor of $2(p+1)$, which is less than $p^2-1$, so the only prime ideals $\mathfrak p$ in $\mathbf Z[A]$ for which $A \bmod \mathfrak p$ might generate $(\mathbf Z[A]/\mathfrak p)^\times$ are prime ideals dividing a prime $p \equiv \pm 1 \bmod 5$, in which case we are in the situation that $A \in \mathbf F_p^\times$ has order $p-1$. Comparing this to the claim up above, since $p-1$ is even when $p > 2$ we see that GRH implies that there are infinitely many primes $p \equiv \pm 1 \bmod 5$ such that $\{F_n \bmod p\}$ has period $p-1$.
Among the 18 odd primes $p \equiv \pm 2 \bmod 5$ with $p < 150$, $\{F_n\bmod p\}$ has period $2(p+1)$ all but 3 times (at $p = 47$ $107$, and $113$). There are many generalizations of the Artin primitive root conjecture and I would not be surprised if one of them can show GRH implies there are infinitely many primes $p \equiv \pm 2 \bmod 5$ such that $\{F_n \bmod p\}$ has period $2(p+1)$, but this is not something I am aware of in more detail at the moment.
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.
