The Fibonacci recurrence (F1 = 1, F2 = 1 and Fn = Fn - 1 + Fn - 2) leads to an infinite sequence of numbers starting with

1, 1, 2, 3, 5,
8, 13, 21, 34, 55,
89, 144, 233, 377, 610, ...

Note that the 5th, 10th and 15th numbers are all divisible by 5.
Show that every fifth number in the sequence is divisible by 5.

When the Fibonacci process is done mod 5, the groups of 5 repeat starting at F(21):

 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0,
 1, 1, 2, 3, 0,

and from then on have to repeat.

Posted by Charlie on 2013-10-21 13:05:30