Proving that there exists $f_n$ such that it is $0$ mod $x$

Question

I have read that after some $n$ in the Fibonacci Sequence, it will eventually repeat because there are only finite remainders considering modulo x. What I am not getting is if there is a sequence such as :$(1,1,2,3 ....)$ how are we sure that there exists a particular $0$ mod $x$? Does the Fibonacci sequence contain all remainders mod $x$? If a particular $a$ mod $x$ is not included in the list? (Something like $(1,1,3,1,1,3)$ sequence does not contain 2) thus there would be

Answer 1

No, the Fibonacci Sequence need not contain all remainders. It is periodic modulo any $x$ though. Consider the Fibonacci Sequence modulo some $x$. Denote the $n$th Fibonacci number by $F_n$ and its remainder modulo $x$ by $a_n$. Then clearly

$$F_n=F_{n-1}+F_{n-2}$$

$$a_n\equiv F_n=F_{n-1}+F_{n-2}\equiv a_{n-1}+a_{n-2}\ (\text{mod }x)$$

Thus, the remainders of the Fibonacci numbers follow the same pattern as the Fibonacci numbers:

$$a_n\equiv a_{n-1}+a_{n-2}\ (\text{mod }x)$$

However, note that there are at most $x^2$ possibilities for $(a_{n-1},a_{n-2})$. These are

$$\{(i,j):0\leq i,j<x\}$$

Since there are a finite number of possibilities, there exists $N$ and $M$ such that

$$(a_{N-1},a_{N-2})=(a_{M-1},a_{M-2})$$

This implies

$$a_N=a_M$$

By induction, you may conclude that $a_n$ is eventually periodic. If you want to extend it to all members of $a_n$, then you have to start with the sequence where it starts to be periodic and then show that this must be the beginning (its not to bad, just another induction proof).