Inductive proof using modular Fibonacci numbers

Question

I need help proving that $F_n$ is a multiple of 3 if and only if n is a multiple of 4.

Where $F_n$ is the nth number in the Fibonacci sequence. I think this can be done using induction, which is ideally the format I would like an answer to be in. I know it has something to do with finding patterns in modular Fibonacci numbers, but I am not sure where to go with this proof.

Thanks.

Answer 1

Consider the sequence $f_n=F_n\pmod{3}$, given by $$ \color{red}{0, 1},1,2,\color{purple}{0},2,2,1,\color{red}{0,1},1,2,\color{purple}{0},\ldots $$ and still fulfilling $f_{n+2}=f_{n+1}+f_n\pmod{3}$.
Since $f_0=f_8$ and $f_1=f_9$, by induction it follows that $$ f_{m} = f_{m\!\pmod{8}} $$ hence $f_m=0$ iff $m$ is a multiple of four.