# Thread: Modulo of fibonacci sequence

1. ## Modulo of fibonacci sequence

Hi everybody,

We can easy observe that result of Fibonacci sequnce according to modulo of a number M is pierodic. However on internet there are proofs like the following:

Perhaps the first thing one notices when the Fibonacci sequence is reduced mod m is that it is periodic. For example, F(mod 4) = 0 1 1 2 3 1 0 1 1 2 3 ... F(mod 5) = 0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 2 3 ...

Any (generalized) Fibonacci sequence modulo m must repeat. After all, there are only $m^2$ possible pairs of residues and any pair will completely determine a sequence both forward and backward. If we ignore the pair 0,0 which gives us the trivial sequence, then we know that the period of any Fibonacci sequence mod m has a maximum length of $m^2-1$.
It will always happen that the first pair to repeat will be the pair we started with. Suppose that this were not so. Then we might have the sequence a,b,...,x,y,...,x,y,... where the pair a,b is not contained in the block x,y,...,x,y. However, we know that this block repeats backward as well as forward, and so the pair a,b cannot be in the sequence. This gives us our contradiction.
Is this claim capable for proof ???

Is it so simple to prove that modulo of fibonacci sequence is periodic???

Thank you all for your time

2. Look Theorem 6 here.

Fernando Revilla