As a start it helps to convert the Fibonacci sequence into a sequence of remainders.

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₁₂, as calculated from the recurrence relation in the problem. Here they are:

f₀

= 0, f₁ = 1, f₂ = 1, f₃ = 2, f₄ = 3, f₅ = 5, f₆ = 8,
f₇

= 13, f₈ = 21, f₉ = 34, f₁₀ = 55, f₁₁ = 89, f₁₂ = 144
.

I observed that f₃, f₆, f₉ and f₁₂ 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₄, f₈ and f₁₂ 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₃ = 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:

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:

f_4q+4

= f_4q+3 + f_4q+2 = (f_4q+2 + f_4q+1) + f_4q+2 = 2f_4q+2 + f_4q+1

= 2(f_4q+1 + f_4q) + f_4q+1 = 3f_4q+1 +f_4q.

In this case 3f_4q+1 is divisible by 3, and so is f_4q (from my hypothesis). I must also say that f₄ = 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.