2006 Alabama ARML TST Problems/Problem 8

Problem

A bored mathematician has his computer calculate 1000 consecutive terms in the Fibonacci sequence. He notes that the smallest of the numbers is a multiple of 7. How many of the other 999 Fibonacci numbers are multiples of 7?

Solution

We list the Fibonacci numbers mod 7:

1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1, 1, ....

So the Fibonacci sequence repeats every 16, and for every 8 numbers, there is one 0. , but we don't count the first one.