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

-
Try writing out the sequence mod 3. –  William D. Dec 7 '11 at 21:58
If you know that $f$ commutes with $gcd$, then it's easy. See en.wikipedia.org/wiki/Fibonacci_number#Divisibility_properties. –  lhf Dec 7 '11 at 22:18
(continuing my comment) ... because $3=f(4)$. –  lhf Dec 7 '11 at 22:24
Very related: math.stackexchange.com/questions/34788/… –  JavaMan Dec 7 '11 at 22:50

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

-
Very nice bringing out of the structure, in a concrete manner. –  André Nicolas Dec 8 '11 at 0:57

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

:)

-

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

-