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 Proof by Tristan)

To recap, my proof was missing a single step.  I need to prove that the fibonacci sequence mod m repeats itself, from the beginning.

In otherwords, I must prove that a sequence like ABCDECDECDE... is impossible (the letters representing pairs of consecutive fibonacci numbers).

This is easily fixed.  ABCDECDECDE... is impossible because C can only be preceded by a unique pair of consecutive fibonacci numbers.  Therefore, B and E must be the same, as well as A and D.  Therefore, the repetition starts over fromt the beginning every time.

This proof was rather trivial, but very necessary to my proof.

Posted by Tristan on 2005-06-11 21:33:01