I'm trying to prove my question using induction, first I tried to prove $4 \mid n \implies 3 \mid F_n$ and I got this:
Setting the base case at $n=0$ I get that $F_0=0\mid 3$ so I took the next $n \in \mathbb{N}$ that is divisible by $4$ that is $n=4$ and $F_4=1+2=3\mid 3$
Let $F_k$ such that $3 \mid F_k$, we'll prove that $3\mid F_{k+4}$
$F_{k+4}=F_{k+3}+F_{k+2}$
$=F_{k+2}+F_{k+1}+F_{k+1}+F_k$
$=F_{k+1}+F_k+F_{k+1}+F_{k+1}+F_k$
$=3F_{k+1}+2F_k$
Since $3 \mid F_k$ by hypothesis then $3 \mid 2F_k$
Clearly $3 \mid 3F_{k+1}$
Here I don't know how to follow, since, for me, it seems that the proof is done. However there's still one implication left, but I don't know how to start it.
Any help will be appreciated.
Best Answer
Working mod $3$, the Fibonacci series is $$1,1,2,0,2,2,1,0,1,1,2,0,\ldots$$
It is easy to prove that this has period $8$, as shown above, with every fourth term being zero, and all the others being nonzero.