In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774.
Definition The Fibonacci numbers are the numbers in the integer sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, ... (sequence A000045 in the OEIS) defined by the recurrence relation
F 0 = 0 {\displaystyle F_{0}=0}
F 1 = 1 {\displaystyle F_{1}=1}
F i = F i − 1 + F i − 2 . {\displaystyle F_{i}=F_{i-1}+F_{i-2}.}
For any integer n, the sequence of Fibonacci numbers Fi taken modulo n is periodic. The Pisano period, denoted π(n), is the length of the period of this sequence. For example, the sequence of Fibonacci numbers modulo 3 begins:
0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ... (sequence A082115 in the OEIS) This sequence has period 8, so π(3) = 8.
Properties
Parity With the exception of π(2) = 3, the Pisano period π(n) is always even. This follows by observing that π(n) is equal to the order of the Fibonacci matrix
Q = [ 1 1 1 0 ] {\displaystyle \mathbf {Q} ={\begin{bmatrix}1&1\\1&0\end{bmatrix}}}
in the general linear group GL 2 ( Z n ) {\displaystyle {\text{GL}}_{2}(\mathbb {Z} _{n})} of invertible 2 by 2 matrices in the finite ring Z n {\displaystyle \mathbb {Z} _{n}} of integers modulo n. Since Q has determinant −1, the determinant of Qπ(n) is (−1)π(n), which is equal to 1 when either n ≤ 2 or π(n) is even.
Pisano periods of composite numbers If m and n are coprime, then π(mn) is the least common multiple of π(m) and π(n). This follows from Chinese remainder theorem. Thus the Pisano periods of composite numbers can be computed by looking at the Pisano periods of prime powers q = pk, for k ≥ 1. If p is prime, π(pk) divides pk–1 π(p). It is unknown if
π ( p k ) = p k − 1 π ( p ) {\displaystyle \pi (p^{k})=p^{k-1}\pi (p)}
for every prime p and integer k > 1. Any prime p providing a counterexample would necessarily be a Wall–Sun–Sun prime, and conversely every Wall–Sun–Sun prime p gives a counterexample (set k = 2). For p = 2 and 5, the exact values of the Pisano periods are known. The periods of powers of these prime powers are as follows:
If n = 2k, then π ( n ) = 3 ⋅ 2 k − 1 = 3 n 2 {\displaystyle \pi (n)=3\cdot 2^{k-1}={\frac {3n}{2}}}
if n = 5k, then π ( n ) = 4 ⋅ 5 k = 4 n {\displaystyle \pi (n)=4\cdot 5^{k}=4n}
From these it follows that if n = 2 k 5k then π(n) = 6n.
Pisano periods of prime numbers
If prime p is different from 2 and 5, then π(p) is a divisor of p2 − 1. This follows from the modulo p analogue of Binet's formula, which implies that π(p) is the multiplicative order of a root of x2 − x − 1 modulo p. Every p other than 2 and 5 lie in the residue classes p ≡ ± 1 ( m o d 10 ) {\displaystyle p\equiv \pm 1\ (\mathrm {mod} \ 10)} or p ≡ ± 3 ( m o d 10 ) {\displaystyle p\equiv \pm 3\ (\mathrm {mod} \ 10)} .
… excerpt ends here. Continue reading the full article.
