The remainders on division by 2 are : 1, 1, 0, 1, 1, 0, 1, 1

The remainders on division by 3 are : 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0

Each term is produced by adding together the two preceding terms, and keeping in mind that these are remainders after division.

So once a pair of consecutive terms appear a second time the sequence must repeat from then on.

The multiples of 2 (or 3) in the original occur where the term is zero in the remainders sequence.

Thank you Andrei from School No. 205 in Bucharest, Romania for taking this further with a more algebraic solution.

First I wrote the Fibonacci numbers up to $f_{12}$, as calculated from the recurrence relation in the problem. Here they are:

${\displaystyle \begin{array}{cc}\multicolumn{1}{c}{f_0}& =0,\hspace{0.5em}{f}_1=1,\hspace{0.5em}{f}_2=1,\hspace{0.5em}{f}_3=2,\hspace{0.5em}{f}_4=3,\hspace{0.5em}{f}_5=5,\hspace{0.5em}{f}_6=8,\\ \multicolumn{1}{c}{f_7}& =13,\hspace{0.5em}{f}_8=21,\hspace{0.5em}{f}_9=34,\hspace{0.5em}{f}_{10}=55,\hspace{0.5em}{f}_{11}=89,\hspace{0.5em}{f}_{12}=144\end{array}.}$

I observed that $f_3,\hspace{0.5em}{f}_6,\hspace{0.5em}{f}_9$ and $f_{12}$ are even. Up to here, $f_n$ is even when $n$ is a multiple of 3. I must prove that such a pattern continues.

I also observed that $f_4,\hspace{0.5em}{f}_8$ and $f_{12}$ are multiples of 3. I could deduce that $f_n$ is a multiple of 3 when $n$ is a multiple of 4.

Now, I must prove the conjectures that I observed. I shall prove them both by induction.

1) $f_n$ - even

$f_3=2$ as calculated before. Let $p$ be a positive integer. I consider that $f_{3p}$ is even. I must prove that $f_{3p+3}$ is also even. From the definition of the Fibonacci Sequence, I obtain:

${\displaystyle f_{3p+3}=f_{3p+2}+f_{3p+1}=(f_{3p+1}+f_{3p})+f_{3p+1}=2f_{3p+1}+f_{3p}.}$

Here, $2f_{3p+1}$ is divisible by 2, and, from my hypothesis, $f_{3p}$ is also divisible by 2. So, $f_{3p+3}$ is divisible by 2.

Hence, by the axiom of induction, $f_n$ is even if $n$ is a multiple of 3.

2) $f_n$ - multiple of 3

Let $q$ be a positive integer. I consider that $f_{4q}$ is a multiple of 3. I shall prove now that $f_{4q+4}$ is a multiple of 3:

${\displaystyle \begin{array}{cc}\multicolumn{1}{c}{f_{4q+4}}& =f_{4q+3}+f_{4q+2}=(f_{4q+2}+f_{4q+1})+f_{4q+2}=2f_{4q+2}+f_{4q+1}\\ \multicolumn{1}{c}{}& =2(f_{4q+1}+f_{4q})+f_{4q+1}=3f_{4q+1}+f_{4q}.\end{array}}$

In this case $3f_{4q+1}$ is divisible by 3, and so is $f_{4q}$ (from my hypothesis). I must also say that $f_4=3$, which is a multiple of 3. Hence by the axiom of induction $f_n$ is a multiple of 3 if $n$ is a multiple of 4.

Editor's note: We should still show that these are the only Fibonnaci numbers divisible by 3 to prove the 'only if' condition.

If any two consecutive Fibonacci numbers have a common factor (say 3) then every Fibonacci number must have that factor. This is clearly not the case so no two consecutive Fibonacci numbers can have a common factor. If $f_n$ and $f_{n+2}$ are both multiples of 3 then $f_{n+1}$ must also be a multiple of 3 and hence all Fibonacci numbers will be multiples of 3 which is not the case. This shows that if $f_n$ and $f_{n+4}$ are multiples of 3 then no Fibonacci numbers between them can be multiples of 3, that is $f_n$ is divisible by 3 only if $n$ is a multiple of 4.