Here's what the Fibonacci sequence modulo m looks like for the first few values

of m.

Fn (mod 2) 1,1,0,1,1,0,1,1,0,1,1,0 ...

Fn (mod 3) 1,1,2,0,2,2,1,0,1,1,2,0,2,2,1. ..

Fn (mod 4) 1,1,2,3,1,0,1,1,2,3,1,0,1,1,2 ...

Fn (mod 5) 1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0, 1, 1,2 ...

Fn (mod 6) 1,1,2,3,5,2,1,3,4,1,5,0,5,5,4,3,1,4,5,3,2,5,1,0,1,1,2,3 ...

Notice in each case that the Fibonacci sequence eventually starts to repeat. In other

words, when we compute the Fibonacci sequence modulo m, we eventually find

two consecutive 1 's appearing, and as soon this happens, the sequence repeats. (We

leave as an exercise for you to prove that this always happens.) Thus there is an

integer N > 1 such that

Fn+N Fn (mod m) for all n = 1, 2, ....