Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Try writing out the sequence mod 3. – Will Dana Dec 7 '11 at 21:58
If you know that $f$ commutes with $gcd$, then it's easy. See – lhf Dec 7 '11 at 22:18
(continuing my comment) ... because $3=f(4)$. – lhf Dec 7 '11 at 22:24
Very related:… – JavaMan Dec 7 '11 at 22:50
up vote 7 down vote accepted

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

share|cite|improve this answer
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$.


share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.