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).

(In reply to re(2): Proof--Quick fix by Nick Hobson)

To Nick Hobson:
That's because C was actually referring to a pair of consecutive numbers.  For example, the sequence 1,1,0,1,1,0,... would be ABCABC... where A is (1,1), B is (1,0), and C is (0,1).  I apologize if this was unclear.

To McWorter:
No, my proof does not work for the Lucas sequence, and does not need to.  It consists of two basic steps.

First, I prove that the fibonacci sequence mod m must repeat the same pattern from the beginning over and over.  This is because any pair of consecutive numbers in the sequence necessarily leads to another unique consecutive pair, and is preceded by a unique consecutive pair.  There is a finite number of possible consecutive pairs, so it must repeat at some point.  Since (1,1) is the first pair that appears, it must repeat sometime at a later point.

Second, I prove that if (1,1) is somewhere in the middle of the sequence, it must be preceded by (0,1), for all m.

This does not work for the Lucas sequence, since I can't easily prove that (1,1) is anywhere in the sequence, though I haven't yet disproved it for the Lucas sequence either.

Posted by Tristan on 2005-06-12 19:30:46