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(3): Proof--Quick fix by Tristan)

Right.  F(0)=0, so your argument shows that, modulo m, 0 must repeat.  Your argument also shows that the Lucas sequence must repeat from the beginning modulo m.  But since no term of the Lucas sequence is 0, there is no guarantee that a term of the Lucas sequence must be divisible by m; e.g.,  modulo 8 the Lucas sequence repeats every 12 terms, but no term is divisible 8.

Posted by McWorter on 2005-06-13 02:16:54