Pisano period

The Pisano period exists for every positive modulus because Fibonacci pairs evolve through a finite set of residue pairs and the recurrence is reversible. Write F₀ = 0, F₁ = 1, and F_n+2 = F_n+1 + F_n. Reducing these values modulo m produces the pair sequence (F_n, F_n+1); its first return to (0, 1) defines π(m).¹

The return is not merely a repetition of one residue: the ordered pair is required. This distinction matters because a zero Fibonacci residue can occur before the complete cycle closes. For example, the sequence modulo 2 is 0, 1, 1, 0, 1, 1, so π(2) = 3. The name honors Leonardo Pisano, better known as Fibonacci, whose sequence is the central example of a linear recurrence in modular arithmetic.⁴

Chinese remainder decomposition makes coprime moduli especially useful: if gcd(m,n) = 1, then π(mn) is the least common multiple of π(m) and π(n).¹ Consequently, factoring the modulus reduces many computations to prime powers. The standard examples are π(2^a) = 3·2^a−1 for a ≥ 1 and π(5^a) = 20·5^a−1; hence π(10^a) = 15·10^a−1.

For a practical calculation, one can iterate pairs, but fast doubling computes F_n in logarithmic time and allows a candidate period to be tested efficiently. The Fibonacci transition matrix [[1,1],[1,0]] also gives a compact method: its powers modulo m encode consecutive Fibonacci numbers. Tables of computed periods, including exceptional small values, are maintained in the On-Line Encyclopedia of Integer Sequences.³

Prime moduli reveal why Pisano periods connect recurrence sequences with finite-field arithmetic. For a prime p other than 2 or 5, the characteristic equation x² − x − 1 = 0 either splits in the field of p elements or splits in its quadratic extension, according to whether 5 is a quadratic residue modulo p. This distinction constrains the possible period and explains recurring divisibility patterns involving p − 1 and p + 1.¹

The period is related to, but different from, the rank of apparition: the latter is the least positive index r for which p divides F_r, whereas the Pisano period requires the full pair (0,1) to return. For composite moduli, prime-power behavior can introduce additional factors, so simply using the period modulo the prime may give an incomplete answer. These relationships place the subject alongside finite fields, quadratic reciprocity, and Lucas sequences.

The most famous unresolved edge case concerns Wall–Sun–Sun primes, hypothetical primes p for which p² divides F_p−(5/p), where (5/p) is the Legendre symbol. Such primes would signal an unusually strong lift of Fibonacci divisibility from p to p²; none are known.²

Another subtlety is that the period need not be close to the modulus: π(24) = 24, but π(25) = 100 and π(29) is much smaller than several elementary upper bounds. Periods therefore reflect factorization and the order of a matrix modulo m rather than a simple linear rule. The same ideas apply to generalized Fibonacci and Lucas recurrences, where changing the initial values or recurrence coefficients changes the return condition and often the arithmetic classification. Wall’s systematic study established many of the foundational divisibility results for these periods.¹

Fibonacci sequence

The sequence defined by F0 = 0, F1 = 1, and Fn+2 = Fn+1 + Fn.

Pisano period π(m)

The least positive k such that Fk ≡ 0 and Fk+1 ≡ 1 modulo m.

Rank of apparition

The least positive index r for which a given modulus divides Fr.

Legendre symbol

A number-theoretic symbol indicating whether an integer is a quadratic residue modulo an odd prime.

Wall–Sun–Sun prime

A hypothetical prime satisfying an unusually strong Fibonacci divisibility condition modulo its square.