Period Count for Fibonacci recurrences modulo primes

Complete prime-modulus classification of both Fibonacci recurrences

Consider the two invertible state-transition matrices

$$U=\begin{pmatrix}0&1\\1&1\end{pmatrix}, \qquad V=\begin{pmatrix}0&1\\1&-1\end{pmatrix} \quad\text{over }\mathbb F_p. \tag{1}$$

Distinct periodic sequences up to cyclic shift correspond exactly to the orbits of these matrices on $\mathbb F_p^2$. The zero state contributes one orbit of length $1$.

We prove every asserted orbit count and orbit-length multiplicity in Marc T. Pudelko's Conjecture 5. We also handle the exceptional primes $2$ and $5$, which require separate treatment. Classical root-order and rank-of-apparition results are discussed by Ballot and Elia; the argument below supplies the complete orbit enumeration requested in the conjecture.

Inert primes

Assume first that $p$ is odd, $p\neq5$, and

$$\left(\frac5p\right)=-1, \qquad\text{equivalently}\qquad p\equiv2,3\pmod5. \tag{2}$$

The characteristic polynomial

$$f(X)=X^2-X-1 \tag{3}$$

is irreducible over $\mathbb F_p$. If $u\in\mathbb F_{p^2}$ is a root, its conjugate is the other root, so

$$u^p=-u^{-1}, \qquad u^{p+1}=-1. \tag{4}$$

Write $t=\operatorname{ord}(u)$. Equation (4) implies

$$t\mid2(p+1), \qquad t\nmid p+1. \tag{5}$$

Consequently

$$t=\frac{2(p+1)}{\alpha}, \qquad \alpha\text{ odd}. \tag{6}$$

Indeed, if $\alpha=2(p+1)/t$ were even, then $t$ would divide $p+1$, contradicting (5).

The companion-matrix identification $\mathbb F_p^2\cong\mathbb F_{p^2}$ identifies $U$ with multiplication by $u$. Every nonzero state therefore has the same orbit length:

$$u^jz=z\quad(z\neq0) \quad\Longleftrightarrow\quad u^j=1. \tag{7}$$

Thus $\pi(p)=t$, and the complete orbit distribution is

$$\boxed{ 1\text{ orbit of length }1, \qquad \frac{p^2-1}{\pi(p)} =\frac{\alpha(p-1)}2 \text{ orbits of length }\pi(p). } \tag{8}$$

In particular,

$$\#_A(p)=1+\frac{\alpha(p-1)}2. \tag{9}$$

Split primes and the two subclasses

Suppose instead that

$$\left(\frac5p\right)=1, \qquad\text{equivalently}\qquad p\equiv1,4\pmod5. \tag{10}$$

Let $u,v\in\mathbb F_p^\times$ be the two roots of $f$, and put

$$v=-u^{-1}, \qquad t=\operatorname{ord}(u), \qquad t'=\operatorname{ord}(v). \tag{11}$$

The root orders satisfy

$$t'= \begin{cases} 2t,&t\text{ odd},\\ t/2,&t\equiv2\pmod4,\\ t,&t\equiv0\pmod4. \end{cases} \tag{12}$$

For odd $t$, adjoining the factor $-1$ doubles the order. For even $t$, use $-1=u^{t/2}$ to obtain

$$v=u^{t/2-1}, \qquad t'=\frac{t}{\gcd(t,t/2-1)}, \tag{13}$$

which gives the remaining two cases.

Diagonalizing $U$, its action becomes

$$(x,y)\longmapsto(ux,vy). \tag{14}$$

Therefore

$$\pi(p)=\operatorname{lcm}(t,t')=\max(t,t'), \qquad \alpha=\frac{p-1}{\pi(p)}. \tag{15}$$

If $t=t'=\pi(p)$, every nonzero state has orbit length $\pi(p)$, and hence

$$\boxed{ \#_{B1}(p) =1+\frac{p^2-1}{\pi(p)} =1+\alpha(p+1). } \tag{16}$$

Otherwise $\{t,t'\}=\{\pi(p)/2,\pi(p)\}$. The eigenline associated with the smaller order contains $p-1$ nonzero states and therefore contributes

$$\frac{p-1}{\pi(p)/2}=2\alpha \tag{17}$$

orbits of length $\pi(p)/2$. Every other nonzero state has orbit length $\pi(p)$, giving

$$\frac{p^2-p}{\pi(p)}=p\alpha \tag{18}$$

such orbits. Thus

$$\boxed{ \#_{B2}(p)=1+2\alpha+p\alpha =1+\alpha(p+2). } \tag{19}$$

This also proves the two requested multiplicities, not merely the total count.

For the canonical Fibonacci initial state, a zero occurs at index $j$ precisely when $u^j=v^j$. In the unequal-order case, write $\pi(p)=2s$, where $s$ is odd, and let $w$ denote the root of order $s$. The other root is $-w^{-1}$, so the quotient of the roots, in one order or the other, is $-w^2$. Because $s$ is odd, this quotient has order $2s=\pi(p)$. Therefore the canonical Pisano cycle contains exactly one zero, as asserted in the conjecture.

If additionally $p\equiv3\pmod4$, then $-1$ is a nonsquare. Since $uv=-1$, exactly one root is a square. Because $p-1\equiv2\pmod4$, the square root has odd order and the other root has even order. Consequently their orders differ, so

$$p\equiv11,19\pmod{20} \quad\Longrightarrow\quad p\text{ belongs to subclass B2}. \tag{20}$$

The parity transform and exceptional primes

The characteristic roots of $V$ are $-u,-v$. Since $uv=-1$,

$$-u=v^{-1}, \qquad -v=u^{-1}. \tag{21}$$

Thus the parity transform interchanges and inverts the two root orders. In the split case this preserves both eigenline lengths and all orbit multiplicities; in the inert case it preserves the common nonzero orbit length. Hence (8), (16), and (19) hold for both recurrences.

Finally, the complete exceptional distributions are

$$\begin{array}{c|c} p&\text{orbit lengths, each occurring once}\\ \hline 2&1,3\\ 5&1,4,20. \end{array} \tag{22}$$

For $p=2$, the three nonzero states form one orbit. For $p=5$, the repeated root is $3$, which has order $4$. Its eigenline contributes the unique orbit of length $4$, while the nontrivial Jordan part has order $5$ and makes every state outside that eigenline have period $20$.

The prime $p=2$ shows that the source's claim that $\alpha$ is odd requires the implicit hypothesis that $p$ is odd: its Pisano period is $3=2(2+1)/2$, so its corresponding $\alpha$ equals $2$. With that necessary endpoint clarification, the full proposed prime classification and both exceptional cases are proved.