Pisano period

Introduction

The Pisano period, named after the Italian mathematician Leonardo Pisano, better known as Fibonacci, is the period with which the sequence of Fibonacci numbers taken modulo \( n \) repeats. This concept is a fascinating intersection of number theory and the properties of the Fibonacci sequence. The Pisano period has applications in various fields, including cryptography, computer science, and mathematical research.

Definition and Basic Properties

The Fibonacci sequence is defined by the recurrence relation: \[ F(n) = F(n-1) + F(n-2) \] with initial conditions: \[ F(0) = 0, \quad F(1) = 1 \]

When considering the Fibonacci sequence modulo \( n \), we denote this sequence as \( F(n) \mod m \). The Pisano period, \( \pi(m) \), is the length of the cycle of the sequence \( F(n) \mod m \).

For example, the Fibonacci sequence modulo 3 is: \[ 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, \ldots \] Here, the sequence repeats every 8 numbers, so the Pisano period \( \pi(3) = 8 \).

Calculation of Pisano Periods

Calculating the Pisano period for a given \( m \) can be computationally intensive. The naive approach involves generating Fibonacci numbers modulo \( m \) until the sequence repeats. However, more sophisticated algorithms can reduce the computational complexity.

The Pisano period \( \pi(m) \) is always finite and can be bounded by: \[ \pi(m) \leq m^2 - 1 \]

For prime \( p \), the Pisano period \( \pi(p) \) is a divisor of \( p-1 \) or \( 2(p+1) \). For composite \( m \), the period can be derived from the periods of its prime factors.

Examples of Pisano Periods

The Pisano periods for small values of \( m \) are as follows:

\( \pi(2) = 3 \)
\( \pi(3) = 8 \)
\( \pi(4) = 6 \)
\( \pi(5) = 20 \)
\( \pi(6) = 24 \)
\( \pi(7) = 16 \)
\( \pi(8) = 12 \)
\( \pi(9) = 24 \)
\( \pi(10) = 60 \)

Mathematical Properties and Theorems

Several theorems describe the properties of Pisano periods:

Theorem 1: Periodicity

The sequence \( F(n) \mod m \) is periodic with period \( \pi(m) \).

Theorem 2: Divisibility

If \( m \) divides \( n \), then \( \pi(m) \) divides \( \pi(n) \).

Theorem 3: Prime Moduli

For a prime \( p \), the Pisano period \( \pi(p) \) divides \( p^2 - 1 \).

Applications

Cryptography

The properties of Pisano periods are used in pseudorandom number generators and cryptographic algorithms. The periodic nature of the sequence modulo \( n \) can be exploited to generate sequences with desirable properties for encryption.

Computer Science

In computer science, Pisano periods are used in algorithms for efficient computation of large Fibonacci numbers modulo \( n \). This has applications in hashing algorithms and data structures.

Mathematical Research

The study of Pisano periods contributes to the broader field of number theory. Researchers investigate the distribution, properties, and implications of these periods in various mathematical contexts.

Image

References

Koshy, Thomas. "Fibonacci and Lucas Numbers with Applications." Wiley-Interscience, 2001.
Knuth, Donald E. "The Art of Computer Programming, Volume 2: Seminumerical Algorithms." Addison-Wesley, 1997.