Number Theory of Fibonacci Numbers

This is a program for studying some number-theoretic properties of Fibonacci numbers.

Number Theory (nt.py)

This module contains some standard number-theoretic functions.

Fibonacci (fibonacci.py)

This module contains the Fibonacci class resresenting a Fibonacci number with a given index, and the FibonacciPrime class, which represents a Fibonacci number with a given prime index. It makes use of the quadratic_integer [4] module to fast compute Fibonacci numbers. It also contains a function pisano_period to compute the Pisano period (see below).

Prime Factors

Fibonacci numbers with composite index greater than 4 are composite [1]. The converse however is false. The FibonacciPrime.lpf() and FibonacciPrime.ppf() methods respectively return the least prime factor and the prime power factorisation (slow for large index) of a given Fibonacci number with prime index [2].

Pisano Period

The Fibonacci sequence modulo n is periodic [1]. The period is known as the Pisano period. pisano_period(n) returns the length of the Pisano period modulo n. [3].

References

[1] Z[phi] and the Fibonacci Sequence Modulo n

[2] On Fibonacci Numbers with Prime Index

[3] Some Divisibility Properties of Fibonacci-Like Sequences

[4] Symbolic Integer Arithmetic in Quadratic Integer Rings