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

This proof to another Fibonacci puzzle also solves the current puzzle.  Substitute m for 10⁶ and m² > m for 10¹².  Then stop at a₀ = a_n.

Posted by Nick Hobson on 2005-06-12 22:39:38