Fibonacci sequence divisible by 3? I have a recursion question for my combinatorial class. I'm looking at the Fibonacci sequence $f(n)=f(n-1)+f(n-2)$ for $n \geq 3$ with $f(1)=f(2)=1$.
I'm trying to prove that $f(n)$ is divisible by 3 if and only if $n$ is divisible by 4. I can see the idea by writing out terms of the sequence, but I'm not sure how to prove the pattern. Can anyone help me in the right direction?
 A: Binet's formula
$$
F(n)=\frac{\varphi^n-\hat\varphi^n}{\sqrt{5}}
$$
where
$$
\varphi=\frac{1+\sqrt{5}}{2},\qquad\hat\varphi=\frac{1-\sqrt{5}}{2}
$$
still holds “modulo $3$” provided we interpret it correctly. In the three element field $\mathbb{F}_3$, $2=5$ is not a square, but we can add a root $\alpha$ of the polynomial $x^2-2$ and consider the extension field $K=\mathbb{F}_3(\alpha)$.
The same proof of Binet's formula on the real numbers shows that the Fibonacci numbers modulo $3$ are of the form
$$
F_3(n)=\frac{\varphi_3^n-\hat\varphi_3^n}{\alpha}
$$
where
$$
\varphi_3=\frac{1+\alpha}{2},\qquad\hat\varphi_3=\frac{1-\alpha}{2}
$$
Let's compute when $\varphi_3^n-\hat\varphi_3^n=0$, that is,
$$
\left(\frac{\varphi_3}{\hat\varphi_3}\right)^{\!n}=1
$$
Now
$$
\frac{\varphi_3}{\hat\varphi_3}=
\frac{1+\alpha}{1-\alpha}=
\frac{1+2\alpha+\alpha^2}{1-\alpha^2}=-2\alpha=\alpha
$$
because $\alpha^2=2$ and $K$ has characteristic $3$.
Thus
$$
\left(\frac{\varphi_3}{\hat\varphi_3}\right)^{\!n}
=\alpha^n
$$
and this is $1$ exactly when $n$ is divisible by $4$, because $\alpha^2=2$ and $2^2=1$ (in $K$).
A: Hint: Prove by induction that
$$f(n)-f(n-8)\text{ is divisible by }3.$$
For the inductive step use the fact that
$$f(n)-f(n-8)=[f(n-1)+f(n-2)]-[f(n-9)+f(n-10)]$$$$=[f(n-1)-f(n-9)]+[f(n-2)-f(n-10)].$$
A: Why don't you try with induction? From a quick look at the Fibonacci sequence, the period of the remainder after division by $3$ is $1,1,2,0,2,2,1,0$. I believe this is easy to prove using induction. But perhaps there is a nicer way, because the induction would be long and not very nice...
A: Just compute the Fibonacci sequence in $\mathbb{Z}_3$, which has only three numbers: $0, 1, 2$. If the result of an addition "overflows," just "wrap" it around, so that $2 + 2 = 1$.
$F_1 = 1$ and $F_2 = 1$ by definition. Then $F_3 = F_1 + F_2 = 1 + 1 = 2$. And $F_4 = F_2 + F_3 = 1 + 2 = 3$. But change it over to $F_4 = 0$.
Then $F_5 = F_3 + F_4 = 2 + 0 = 2$, $F_6 = F_4 + F_5 = 0 + 2 = 2$, and then $F_7 = F_5 + F_6 = 2 + 2 = 4$ which we wrap around to $= 1$. Which leads us to $F_8 = F_6 + F_7 = 2 + 1 = 3$ which wraps around to $= 0$.
Clearly the whole pattern is going to repeat, because $\mathbb{Z}_3$ will not unexpectedly sprout more numbers.
