Period of Fibonacci Numbers Over Finite Fields

finite-fieldsnt.number-theory

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

Best Answer

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$.