# $f_n$ is divisible by $4$ if and only if $n$ is divisible by $6$

I thought I had this question down, but while looking over my solution, I think I'm missing a step.

I want to show for $f_n$ the nth fibonacci number, that $f_n$ is divisible by $4$ if and only if $n$ is divisible by $6$.

I approach this with strong induction. I was able to prove the backward implication by assuming the result holds for all $f_k$ up to $n$, and rewriting $f_{n+1}=8f_{n-4}+5f_{n-5}$. Also, I was able to prove that $f_n$ is divisible by $2$, if and only if $n$ is divisible by $3$ by rewriting $f_{n+1}=2f_{n-1}+f_{n-2}$.

I guess it remains to show that $f_{n+1}$ divisible by $4$ implies that $n$ is even, and thus $n$ will be divisible by $6$, but I just can't figure out how to show this last part. I've messed with proofs by contradiction, the contrapositive, but have come up with nothing. How would one do that?

One way to look at it is to consider the sequence in $\mathbb{Z}/4\mathbb{Z}$. Same definition: $f_1=f_2=1$ and $f_{n+1}=f_{n}+f_{n-1}$. The sequence hence starts as follows: 1, 1, 2, 3, 1, 0, 1, 1, ... Clearly the sequence is periodic of period 6. You can probably find a way to write this hand-wavy argument more rigorously.
• All I think you need to say is the sequence modulo 4 starts 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, that $f_{n+6} \equiv f_n \pmod{4}$ is the inductive hypothesis, and we know $f_{n-1}+f_{n-2} = f_{n}$ so $f_{n+6} = f_{n+5} + f_{n+4}$ – Henry Mar 7 '11 at 0:15
• @Minh Can this fact be used to prove $p\rightarrow q$ and $q\rightarrow p$? – Hopmaths yesterday
Let's compute the Fibonacci sequence modulo $4$: $$0,1,1,2,3,1,0,1,\ldots$$ Here the sequence repeats, since $0,1$ is where we started. We get that $$F_n \equiv F_{n \mod{6}} \pmod{4},$$ since $F_n \mod{4}$ is cyclic, with cycle of size $6$. Examining the first $6$ remainders, we see that only $F_0 \equiv 0 \pmod{4}$, hence your question.