Why do all primes in Fibonacci numbers repeat so regularly

Question

I watched this YouTube video that is mainly about primes as factors of the Fibonacci numbers. It notes that every Fibonacci number after F(12) has a new prime factor not previously seen, and this new prime factor will also divide all multiples of that index. Why this works is demonstrated for every third Fibonacci number being even, and extending this argument to other primes is left as an exercise for the viewer. However in the case of 2, the entire cycle repeats every 3 steps. That is to say that mod 2, every Fibonacci number is the same as the one 3 prior.

Whereas for 5, for example, every 5th Fibonacci number is divisible by 5, but the cycle doesn't fully repeat until every 20. I understand why this larger cycle exists, that mod 5, every F(n) is equivalent to F(n-20), but not why the smaller cycle exists within it. I have found many examples where the Fibonacci numbers are cyclical mod some prime only 2 or 4 times the first appearance. For example again, F(11) is 89. For any n divisible by 11, F(n) will have 89 as a factor. And mod 89, F(n) is equivalent to F(n-44). For other primes, the Fibonacci numbers repeat after 2 cycles, such as 47, which first appears as a factor in F(16) and mod 47, F(n)=F(n-32).

Why even with these larger cycles do the primes reappear as factors so periodically along the way?

Answer 1

Let $m$ be any integer $> 1$ (not just a prime), and consider the pairs $P_n = (F_n, F_{n+1})$ mod $m$. $P_{n+1}$ is determined by $P_n$ (as $F_{n+2} = F_{n} + F_{n+1}$), but also $P_n$ is determined by $P_{n+1}$ (as $F_{n} = F_{n+2} - F_{n+1}$). There are at most $m^2$ possible values for $P_n$, so eventually there is a repetition: $P_j = P_{j+k}$ for some $j$ and $k > 0$. But then because each $P_n$ determines all the others, we must have $P_n = P_{n+k}$ for all $n$, i.e. the Fibonacci numbers mod $m$ are periodic with period $k$. The least $k$ for a given $m$ is called the Pisano period of $m$.

EDIT: If we write the $P_n$ as column vectors, $P_{n+1} \equiv \pmatrix{0 & 1\cr 1 & 1\cr} P_n \mod m$. If $M$ is the matrix $\pmatrix{0 & 1\cr 1 & 1\cr}$, this implies $P_{n+k} \equiv M^k P_n \mod m$. Typically (since there are only $m$ possible values for $F_j$ mod $m$) there will be some $q$ less than the Pisano period for which $F_q \equiv 0 \mod m$. Thus $P_0 = \pmatrix{0\cr 1\cr}$ while $P_q = \pmatrix{0 \cr t\cr} = t \pmatrix{0\cr 1\cr}$ where $t \ne 1$. Then by linearity, for any positive integer $j$ we'll have $P_{jq} \equiv t^j P_0 \mod m$, and in particular $F_{jq} \equiv 0 \mod m$. This gives you your "smaller cycle".

Answer 2

First, credit to Robjohn for this answer which led me to understanding the answer.

F(n) mod m will at some point be zero. From there, the sequence will be 0, a, a,... From there the smaller cycle will repeat mod m but a times larger.

For example F(11) is 89, so mod 89, it is 0. After that mod 89 the next values F(12) and F(13) are both 55 mod 89. The small cycle of F(12) through F(22) will be the same as F(1) through F(11) in each case multiplied by 55 mod 89. So F(22) and F(33) and so on must also be 0 mod 89.

Once 55 raised to some power reaches 1 mod 89, the whole cycle repeats from 1. This happens at 55^4, so the larger cycle repeats after 4*11 or 44 steps.