Friday, February 20, 2009

Fibonacci modulo m

The general problem of the periods of the Fibonacci sequence modulo m is definitely non-trivial (with the case m = p - prime - playing a very important role). An important reference can be found here ("The Fibonacci Sequence Under Various Moduli" - M.Sc. Thesis by Marc Renault, 1996). Also see the article (PDF) "The Fibonacci sequence modulo p^2...".

An example that teachers use relatively often as a middle-school problem: "Find the period of the sequence of the last digits of the Fibonacci numbers"! That will correspond to the modulus m=10, the answer is 60, and the elements of the period are
0,1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,0,
9,9,8,7,5,2,7,9,6,5,1,6,7,3,0,3,3,6,9,5,4,9,3,2 ,5,7,2,9,1
If the modulus m is 2011 (that is the 305-th prime), the period of the Fibonacci sequence modulo m is 2010.