Contents

Pisano PeriodEdit

The Pisano period is a fundamental concept in the study of Fibonacci numbers as they appear in modular arithmetic. In short, it is the period with which the Fibonacci sequence repeats modulo an integer m. The topic sits at the intersection of number theory and combinatorics and has practical consequences for fast modular computations and for understanding the behavior of integer sequences under reduction.

The term is named in honor of the medieval Italian mathematician Leonardo Pisano Bigollo, better known as Fibonacci, who studied Fibonacci numbers in the 13th century. The idea of examining remainders of the Fibonacci sequence modulo various moduli has since grown into a well-developed area of study, with a formal object now standard in textbooks and research alike: the Pisano period, often denoted π(m). Fibonacci numbers

Definition and notation

Let F(n) denote the nth Fibonacci number, with F(0) = 0 and F(1) = 1, and consider the sequence F(n) modulo m. Because there are only finitely many pairs (F(n) mod m, F(n+1) mod m), the sequence of pairs is eventually periodic. In fact, the sequence of residues is purely periodic starting from n = 0, and the period is the smallest positive integer π(m) such that

  • F(π(m)) ≡ 0 (mod m) and
  • F(π(m) + 1) ≡ 1 (mod m).

Equivalently, the pair (F(n) mod m, F(n+1) mod m) returns to (0, 1) after π(m) steps. The number π(m) is the Pisano period of modulus m. This value encodes a compact description of the repeating pattern of Fibonacci numbers when viewed through the lens of modular reduction. See also Modular arithmetic and Periodicity for related ideas.

Basic properties

  • Existence and finiteness: For every positive integer m, the sequence of Fibonacci residues modulo m is periodic, so π(m) exists and is finite. The period is always at least 1 and never exceeds a finite bound that depends on m. See also Fibonacci sequence for the underlying recurrence that generates the sequence being reduced.
  • Coprime moduli behavior: If gcd(a, b) = 1, then the period modulo ab is closely related to the periods modulo a and modulo b. In particular, π(ab) divides the least common multiple of π(a) and π(b). In many cases (but not every one) one has π(ab) = lcm(π(a), π(b)). The exact behavior can depend on subtle arithmetic properties of a and b. See Lcm and Quadratic residues for related concepts.
  • Prime powers: The behavior of π(p^k) for a prime p and integer k ≥ 1 is a central area of study. A widely used rule of thumb, with specific caveats, is that for odd primes p not equal to 5, π(p^k) tends to equal p^{k−1} · π(p). Special cases occur for p = 2 and p = 5, which have their own characteristic formulas (for instance, π(2^k) = 3 · 2^{k−1} and π(5^k) = 20 · 5^{k−1} for k ≥ 1). See Legendre symbol and Quadratic residues for related number-theoretic tools.
  • Computation and upper bounds: A straightforward way to determine π(m) is to generate Fibonacci numbers modulo m until the pair (0, 1) reappears. More advanced methods use properties of the Fibonacci Q-matrix, matrix exponentiation, and the order of elements in the ring Fibonacci numbers to accelerate computation. See Matrix exponentiation and Fibonacci Q-matrix if you want to explore the matrix viewpoint.

Computation and algorithms

  • Direct iteration: Compute F(n) mod m iteratively with F(n+1) = F(n) + F(n−1) (mod m) until the pair (F(n), F(n+1)) returns to (0, 1). The number of steps needed is π(m). This method is simple but can be slow for large m.
  • Fast doubling and modular arithmetic: The fast doubling identities allow F(n) to be computed in O(log n) time using only modular arithmetic, which helps when testing candidate periods or when π(m) is large. See Fast doubling method and Modular arithmetic for background.
  • Prime-power and factorization approaches: When m factors into coprime prime powers, π(m) often relates to π(p^k) for each factor, with refinements needed for 2- and 5-adic behavior. Factorization of m and knowledge of π(p) for primes p dividing m can lead to efficient calculations of π(m). See Prime factorization and Fibonacci numbers for related topics.

Examples and notable values

  • π(10) = 60: The last digits of Fibonacci numbers repeat every 60 terms. This concrete example illustrates how a small modulus yields a relatively modest period compared with the size of the modulus.
  • Small moduli: π(2) = 3, π(3) = 8, π(4) = 6, and π(5) = 20. These illustrate how the period can vary nontrivially with m, even for small numbers.
  • General insights: For many odd primes p with 5 as a quadratic residue modulo p, π(p) divides p − 1; when 5 is a nonresidue, π(p) divides p + 1. These divisibility patterns connect the Pisano period to quadratic reciprocity and the Legendre symbol Legendre symbol.

Generalizations and related topics

  • Variants with Lucas sequences: Similar periodicity phenomena occur for Lucas sequences modulo m, yielding related period concepts and applications.
  • Other moduli and residue patterns: The study of π(m) intersects with questions about modular recurrence relations, dynamical systems over finite rings, and computational number theory.
  • Practical applications: Knowledge of Pisano periods informs algorithm design for fast modular Fibonacci computations, random number generation, and certain combinatorial counting problems where reductions modulo m arise naturally. See Fibonacci numbers, Matrix exponentiation, and Modular arithmetic for background.

See also