Fibonacci divisibility

Question

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).

Answer 1

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$.

Answer 2

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$.