The Fibonacci sequence goes F(0)=0, F(1)=1, and for n>1, F(n)=F(n-1)+F(n-2).

Show that for every positive integer m there exists an integer n>0 such that m divides F(n).

Consider all of the fibonacci numbers, mod m.  Since there is a limited number (mē) of possible pairs of consecutive fibonacci numbers, this sequence must repeat at some point.  I must prove that before repeating, at least one zero appears.

Perhaps it would help to find how often it repeats. I made the following chart, determined by brute force, in hopes of achieving inspiration. Let R be the repeating length.

m  R  sequence
2  3  1,1,0
3  8  1,1,2,0,2,2,1,0
4  6  1,1,2,3,1,0
5  20 1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0
6  24 1,1,2,3,5,2,1,3,4,1,5,0,5,5,4,3,1,4,5,3,2,5,1,0
7  16 1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0
8  12 1,1,2,3,5,0,5,5,2,7,1,0
9  24 1,1,2,3,5,8,4,3,7,1,8,0,8,8,7,6,4,1,5,6,2,8,1,0
10 60 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,0

Well, I don't know about the reader, but inspiration has certainly hit me.

The last number of the repeating sequence must always be a 0, preceded by a 1.  No other two numbers will result in repeating the 1,1 consecutive pair.  QED

All those numbers in the chart seem to follow a few interesting patterns, and I'm slightly disappointed that I didn't have to understand any of them in order to solve this problem.  But then again, I'm not sure I could ever understand them.

EDIT:  I've realized that there may be a flaw in this proof.  I proved that the sequence must repeat, but I didn't prove that it must repeat from the beginning.  For example, it could go ABCDECDECDECDE...  I'll try again later.

Edited on June 11, 2005, 9:20 pm

Posted by Tristan on 2005-06-11 21:14:07