The Pisano period of C-finite sequences

Problem definition

The Pisano period of a prime pp, is defined as the minimum integer π(p)\pi(p) satisfying f0≡fπ(p),f1≡fπ(p)+1(mod⁡p)f_0\equiv f_{\pi(p)},f_1\equiv f_{\pi(p)+1}(\operatorname{mod} p), where ff is the Fibonacci sequence. It is well known that for p≠2,5p\not=2,5, π(p)\pi(p) is either a divisor of p−1p-1 or 2p+22p+2. In this article, we extend this conclusion to any C-finite sequence of the formulae fn≡afn−1+fn−2(mod⁡p)f_n\equiv af_{n-1}+f_{n-2}(\operatorname{mod} p), where a∈Zpa\in\mathbb{Z}_p is a constant.

Closed form expression

Assume fnf_n has a general form rnr^n. Then we rewrite the recursive formulae as rn≡arn−1+rn−2r^n\equiv ar^{n-1}+r^{n-2}, which yields a characteristic equation r2−ar−1≡0r^2-ar-1\equiv 0. Let λ1,λ2\lambda_1,\lambda_2 be the characteristic roots. Assume f0=0,f1=1f_0=0,f_1=1, W.L.O.G., We claim that:

fn≡λ1n−λ2nλ1−λ2f_n\equiv\frac{\lambda_1^n-\lambda_2^n}{\lambda_1-\lambda_2}

Proof: since fn−1≡λ1n−1−λ2n−1λ1−λ2f_{n-1}\equiv\frac{\lambda_1^{n-1}-\lambda_2^{n-1}}{\lambda_1-\lambda_2} and fn−2≡λ1n−2−λ2n−2λ1−λ2f_{n-2}\equiv\frac{\lambda_1^{n-2}-\lambda_2^{n-2}}{\lambda_1-\lambda_2},

afn−1+fn−2≡aλ1n−1−aλ2n−1+λ1n−2−λ2n−2λ1−λ2≡λ1n−2(aλ1+1)−λ2n−2(aλ2+1)λ1−λ2≡λ1n−λ2nλ1−λ2≡fn\begin{aligned} af_{n-1}+f_{n-2}&\equiv\frac{a\lambda_1^{n-1}-a\lambda_2^{n-1}+\lambda_1^{n-2}-\lambda_2^{n-2}}{\lambda_1-\lambda_2}\\ &\equiv\frac{\lambda_1^{n-2}(a\lambda_1+1)-\lambda_2^{n-2}(a\lambda_2+1)}{\lambda_1-\lambda_2}\\ &\equiv\frac{\lambda_1^n-\lambda_2^n}{\lambda_1-\lambda_2}\\ &\equiv f_n \end{aligned}

Pisano period

As aforementioned, the characteristic roots should satisfy r2−ar−1≡0r^2-ar-1\equiv 0 or (2r−a)2≡a2+4(mod⁡p)(2r-a)^2\equiv a^2+4(\operatorname{mod}p). If ∃w∈Zp\exists w\in\mathbb{Z}_p such that w2≡a2+4(mod⁡p)w^2\equiv a^2+4(\operatorname{mod} p), it is straightforward to derive 2λ1−a≡w2\lambda_1-a\equiv w and 2λ2−a≡−w2\lambda_2-a\equiv-w and thus λ1,λ2∈Zp\lambda_1,\lambda_2\in\mathbb{Z}_p. Then by Fermat’s little theorem, λ1p−1≡λ2p−1≡1\lambda_1^{p-1}\equiv\lambda_2^{p-1}\equiv 1 and:

fn+p−1≡λ1n+p−1−λ2n+p−1λ1−λ2≡λ1n−λ2nλ1−λ2≡fnf_{n+p-1}\equiv\frac{\lambda_1^{n+p-1}-\lambda_2^{n+p-1}}{\lambda_1-\lambda_2}\equiv\frac{\lambda_1^n-\lambda_2^n}{\lambda_1-\lambda_2}\equiv f_{n}

which implies that the Pisano period π(p)∣(p−1)\pi(p)|(p-1).

If ∄w∈Zp\not\exists w\in\mathbb{Z}_p such that w2≡a2+4(mod⁡p)w^2\equiv a^2+4(\operatorname{mod} p), we claim that π(p)∣(2p+2)\pi(p)|(2p+2).

Proof: since λ1,λ2\lambda_1,\lambda_2 are the roots of the equation r2−ar−1≡0r^2-ar-1\equiv 0, λ1+λ2≡a\lambda_1+\lambda_2\equiv a and λ1λ2≡−1\lambda_1\lambda_2\equiv -1.

(λ1+λ2)p≡λ1p+λ2p≡ap(\lambda_1+\lambda_2)^p\equiv \lambda_1^{p}+\lambda_2^p\equiv a^p

Let w=2λ1−aw=2\lambda_1-a. Then:

(w+a)p2−p+λ2p≡ap(w+a)^p2^{-p}+\lambda_2^p\equiv a^p

Note that λ1,λ2,w∉Zp\lambda_1,\lambda_2,w\not\in\mathbb{Z}_p and 2,a∈Zp2,a\in\mathbb{Z}_p. Therefore, (2−1)p−1≡ap−1≡1\left(2^{-1}\right)^{p-1}\equiv a^{p-1}\equiv 1 by Fermeat’s little theorem:

(w+a)p+2λ2p≡2ap⇒wp+2λ2p≡ap≡a⇒λ2p≡2−1(a−wp)\begin{aligned} &\quad (w+a)^p+2\lambda_2^p\equiv 2a^p\\ &\Rightarrow w^p+2\lambda_2^p\equiv a^p\equiv a\\ &\Rightarrow \lambda_2^p\equiv 2^{-1}(a-w^p) \end{aligned}

By quadratic reciprocity, wp−1≡(a2+4)p−12≡−1w^{p-1}\equiv (a^2+4)^{\frac{p-1}{2}}\equiv -1, then:

λ2p≡2−1(a+w)≡λ1\lambda_2^p\equiv2^{-1}(a+w)\equiv \lambda_1

Then λ2p+1≡λ1λ2≡−1\lambda_2^{p+1}\equiv \lambda_1\lambda_2\equiv -1 and λ22p+2≡1\lambda_2^{2p+2}\equiv 1. Similarly, we can prove λ12p+2≡1\lambda_1^{2p+2}\equiv 1 by assuming w=2λ2−aw=2\lambda_2-a. Therefore:

fn+2p+2≡λ1n+2p+2−λ2n+2p+2λ1−λ2≡λ1n−λ2nλ1−λ2≡fnf_{n+2p+2}\equiv\frac{\lambda_1^{n+2p+2}-\lambda_2^{n+2p+2}}{\lambda_1-\lambda_2}\equiv\frac{\lambda_1^n-\lambda_2^n}{\lambda_1-\lambda_2}\equiv f_n