Pisano period
In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats.
The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774.
[1][2] The Fibonacci numbers are the numbers in the integer sequence: defined by the recurrence relation For any integer n, the sequence of Fibonacci numbers Fi taken modulo n is periodic.
For example, the sequence of Fibonacci numbers modulo 3 begins: This sequence has period 8, so π(3) = 8.
A proof of this can be given by observing that π(n) is equal to the order of the Fibonacci matrix in the general linear group
of invertible 2 by 2 matrices in the finite ring
Thus the study of Pisano periods may be reduced to that of Pisano periods of prime powers q = pk, for k ≥ 1.
The periods of powers of these primes are as follows: From these it follows that if n = 2 · 5k then π(n) = 6n.
The remaining primes all lie in the residue classes
If p is a prime different from 2 and 5, then the modulo p analogue of Binet's formula implies that π(p) is the multiplicative order of a root of x2 − x − 1 modulo p. If
(by quadratic reciprocity again), and belong to the finite field As the Frobenius automorphism
That is r 2(p+1) = 1, and the Pisano period, which is the order of r, is the quotient of 2(p+1) by an odd divisor.
The first twelve Pisano periods (sequence A001175 in the OEIS) and their cycles (with spaces before the zeros for readability) are[5] (using X and E for ten and eleven, respectively): The first 144 Pisano periods are shown in the following table: If n = F(2k) (k ≥ 2), then π(n) = 4k; if n = F(2k + 1) (k ≥ 2), then π(n) = 8k + 4.
That is, if the modulo base is a Fibonacci number (≥ 3) with an even index, the period is twice the index and the cycle has two zeros.
If the base is a Fibonacci number (≥ 5) with an odd index, the period is four times the index and the cycle has four zeros.
For odd k, the cycle has only one zero, and the second half of the cycle, which is of course equal to the part on the left of 0, consists of alternatingly numbers F(2m + 1) and n − F(2m), with m decreasing.
For generalized Fibonacci sequences (satisfying the same recurrence relation, but with other initial values, e.g. the Lucas numbers) the number of occurrences of 0 per cycle is 0, 1, 2, or 4.
The ratio of the Pisano period of n and the number of zeros modulo n in the cycle gives the rank of apparition or Fibonacci entry point of n. That is, smallest index k such that n divides F(k).
They are: In Renault's paper the number of zeros is called the "order" of F mod m, denoted
Pisano periods can be analyzed using algebraic number theory.
Thus it suffices to compute Pisano periods for prime powers
For prime numbers p, these can be analyzed by using Binet's formula: If k2 + 4 is a quadratic residue modulo p (where p > 2 and p does not divide k2 + 4), then
can be expressed as integers modulo p, and thus Binet's formula can be expressed over integers modulo p, and thus the Pisano period divides the totient
If k2 + 4 is not a quadratic residue modulo p, then Binet's formula is instead defined over the quadratic extension field
, which has p2 elements and whose group of units thus has order p2 − 1, and thus the Pisano period divides p2 − 1.
For example, for p = 3 one has π1(3) = 8 which equals 32 − 1 = 8; for p = 7, one has π1(7) = 16, which properly divides 72 − 1 = 48.
This analysis fails for p = 2 and p is a divisor of the squarefree part of k2 + 4, since in these cases are zero divisors, so one must be careful in interpreting 1/2 or
For p = 2, k2 + 4 is congruent to 1 mod 2 (for k odd), but the Pisano period is not p − 1 = 1, but rather 3 (in fact, this is also 3 for even k).
One can consider Fibonacci integer sequences and take them modulo n, or put differently, consider Fibonacci sequences in the ring Z/nZ.
Table of the extra cycles: (the original Fibonacci cycles are excluded) (using X and E for ten and eleven, respectively) Number of Fibonacci integer cycles mod n are:
