Prove for Fibonacci numbers: $3\mid f(n) \iff  4\mid n$ Let $f(n)$ be the $n$th Fibonacci number.
Prove that $$3\mid f(n) \iff  4\mid n$$

I tried to use induction to prove it but I couldn't continue when I reached $n+1$ case.
 A: Let $g(n)=f(n)\bmod 3$. Then $g(0)=0$, $g(1)=1$, and $g(n+1)=\big(g(n)+g(n-1)\big)\bmod 3$ for $n>0$. The next few values are $g(2)=1$, $g(3)=2$, $g(4)=(1+2)\bmod 3=0$, and $g(5)=2$. Continuing in that vein, we can compute the following values, where I’ve starred the rows in which $3\mid f(n)$:
$$\begin{array}{c|c|cc}
n&f(n)&g(n)&\\ \hline
0&0&0&*\\
1&1&1\\
2&1&1\\
3&2&2\\
4&3&0&*\\
5&5&2\\
6&8&2\\
7&13&1\\ \hline
8&21&0&*\\
9&34&1\\
\end{array}$$
Can you see why I put a bar between $n=7$ and $n=8$? Remember, each value of $f$ or $g$ depends only on the immediately preceding two values. The induction with $g(n)$ is a little easier to see than the induction with $f(n)$.
A: Hint: use the recurrence three times to write $f_{n+1}=3f_{n-2}+2f_{n-3}$. Then use the induction hypothesis, and the fact that $3\mid 2a \Longleftrightarrow 3 \mid a$ for any integer $a$.
:)
A: HINT $\ $ Show $\rm\ f_{\:n} \equiv\: -f_{\:n-4}\pmod 3\:,\:$ which immediately yields the sought result.
The above congruence is a special case $\rm\:k = 4\:$ of a more general law: $\rm\:f_{\:n}\equiv f_{\:k-1}\ f_{\:n-k} \pmod{f_{\:k}}\:.\:$
This leads to a simple inductive proof that $\rm\:gcd(f_n,f_k) = f_{\:gcd(n,k)}\:,\ $  so $\rm\ f_{\:k}\ |\ f_{\:n}\ \iff\ k\ |\ n\:.\ $
Specializing $\rm\:k = 4\:$ yields $\rm\ 3\ |\ f_{\:n}\ \iff\ 4\ |\ n\:.$
