Pisano period

In number theory, the nth Pisano period, written as pi(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. 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, ... defined by the recurrence relation For any integer n, the sequence of Fibonacci numbers Fi taken modulo n is periodic. The Pisano period, denoted pi(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, ... This sequence has period 8, so pi(3) = 8. With the exception of pi(2) = 3, the Pisano period pi(n) is always even. A simple proof of this can be given by observing that pi(n) is equal to the order of the Fibonacci matrix in the general linear group GL2(Zn) of invertible 2 by 2 matrices in the finite ring Zn of integers modulo n. Since Q has determinant −1, the determinant of Qpi(n) is (−1)pi(n), and since this must equal 1 in Zn, either n ≤ 2 or pi(n) is even. If m and n are coprime, then pi(mn) is the least common multiple of pi(m) and pi(n), by the Chinese remainder theorem. For example, pi(3) = 8 and pi(4) = 6 imply pi(12) = 24. Thus the study of Pisano periods may be reduced to that of Pisano periods of prime powers q = pk, for k ≥ 1. If p is prime, pi(pk) divides pk–1 pi(p). It is unknown if 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). So the study of Pisano periods may be further reduced to that of Pisano periods of primes. In this regard, two primes are anomalous.