Is it true that the Fibonacci sequence has the remainders when divided by 3 repeating? [duplicate]

A sequence like the Fibonacci sequence is completely determined by any of its segments of length $2$. Modulo any number $N$ (not just $3$) there are only finitely many possible segments of length $2$, in fact there are $N^2$ of them, so the sequence of remainders will eventually repeat itself and become periodic.

E.g.

• modulo $5$ : $0$, $1$, $1$, $2$, $3$, $0$, $3$, $3$, $1$, $4$, $0$, $4$, $4$, $3$, $2$, $0$, $2$, $2$, $4$, $1$, $0$, $1$, ... (got back to the $0$, $1$ segment);

• modulo $7$ : $0$, $1$, $1$, $2$, $3$, $5$, $1$, $6$, $0$, $6$, $6$, $5$, $4$, $2$, $6$, $1$, $0$, $1$, ... (got back to the $0$, $1$ segment again).

It is an interesting "exercise" to compute the length of the period of the sequence modulo a prime $p$ without actually computing the whole sequence.

They have to repeat. The two-term recursion $$F_n=F_{n-1}+F_{n-2}$$ yields the same recursion modulo $3$ for your modified sequence: $$f_n=f_{n-1}+f_{n-2}\mod 3$$ Each of the values can only take on $3$ distinct values, so there are at most $9$ different combinations of $f_{n-1}$ and $f_{n-2}$. It has to repeat after at most $9$ steps for any two-term recursion (not just the above), but for some, it may even repeat before that.

You can draw yourself a $3\times 3$ table and trace the path the sequence of ($f_{n-1}$,$f_{n-2}$) takes. It goes like (1,1), (1,2), (2,0), (0,2), (2,2), (2,1), (1,0), (0,1)...

You see that $(0,0)$ is not visited.

Since $f(n)=f(n-1)+f(n-2)$ the remainder when dividing by three of $f_n$ can be obtained by knowing the remainder of the other two numbers.

You just proved that the sequence starts $1,1,2,0,2,2,1,0,1,1$ After this we have to do exactly the same deduction we made at the beginning. Hence they do cycle.