Fibonacci divisibility Prove that the following holds: $3|F_n$ if and only if $4|n$
Base case for $n=1$: 
$F_1$=1, so $F_1$ is not divisible by 3 and 1 is not divisble by 4.
So the proposition holds for $k=1$
Continue for n=2, n=3 and n=4.
Inductive step
Assume $3|F(4k)$. We now have to prove that the proposition also holds for $4(k+1)=4k+4$.
$F(4k+4)=F(4k+3)+F(4k+2)=2F(4k+2)+F(4k+1)=3F(4k+1)+2F(4k)=5F(4k)+3F(4k-1)$
$5F(4k)$ is divisible by 3 by our hypothesis and it is obvious that $3F(4k-1)$ is divisible by 3.
$F(4k+3)=3F(4k)+2F(4k-1)$
$3F(4k)$ is divisble by 3 by our hypothesis and since $n$ already is a multiple of 4 $(n-1)$ can't possibly be a multiple of 4 to. So by our hypothesis $2F(4k-1)$ is not divisible by 3 and thus $F(4k+3)$ is not divisible by 3.
I continue the proof for $F(4k+2)$ and $F(4k+1)$ and conclude that by induction $3|F_n$ holds if $4|n$ holds, but the proposition involves a bi-implication, so I need to prove that $4|n$ holds if $3|F_n$ holds. However, I don't know where to begin.
I also think my proof is too lengthy. So I would like to know if there is a simpler, more elegant way to prove the proposition (induction is not required). 
 A: Consider the sequence $R_k$ of reminders modulo 3 instead.
This is:
$$
R_1 = 1\\
R_2 = 1\\
R_3 = 2\\
R_4 = 0\\
R_5 = 2\\
R_6 = 2\\
R_7 = 1\\
R_8 = 0\\
$$
and the values repeat exactly. Hence $R_k = 0\iff 4|k$.
A: Along the lines off mookid:
Lemma: In mod 3 arithmetic,  for all $k \in \Bbb{N}$,
$$
\begin{array}{c}
F_{8k-7} \equiv 1 \\
F_{8k-6} \equiv 1 \\
F_{8k-5} \equiv 2 \\
F_{8k-4} \equiv 0 \\
F_{8k-3} \equiv 2 \\
F_{8k-2} \equiv 2 \\
F_{8k-1} \equiv 1 \\
F_{8k}   \equiv 0 \\
\end{array}
$$
Proof:  The basis is trivially established by inspecting $F_1$ through $F_8$.  Assume
the Lemma for  $k$.  Then
$$
\begin{array}{c}
F_{8(k+1)-7} = F_{8k+1} \equiv F_{8k} + F_{8k-1} = 0+1 = 1 \\
F_{8(k+1)-6} = F_{8k+2} \equiv F_{8k+1} + F_{8k} = 1+0 = 1 \\
F_{8(k+1)-5} = F_{8k+3} \equiv F_{8k+2} + F_{8k+1} = 1+1 = 2 \\
F_{8(k+1)-4} = F_{8k+4} \equiv F_{8k+3} + F_{8k+2} = 2+1 = 0 \\
F_{8(k+1)-3} = F_{8k+5} \equiv F_{8k+4} + F_{8k+3} = 0+2 = 2 \\
F_{8(k+1)-2} = F_{8k+6} \equiv F_{8k+5} + F_{8k+4} = 2+0 = 2 \\
F_{8(k+1)-1} = F_{8k+7} \equiv F_{8k+6} + F_{8k+5} = 2+2 = 1 \\
F_{8(k+1)} = F_{8k+8} \equiv F_{8k+7} + F_{8k+6} = 2+1 = 0 
\end{array}
$$
This establishes induction so the lemma is true.
Finally, the theorem to be proved can be read from the lemma, by noting that only $F_{8k-4}$ and $F_{8k}$ are zero mod $3$.
