Fibonacci Factors

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_{12}$, as calculated from the recurrence relation in the problem. Here they are: 

$$\eqalign{ f_0 &= 0,\ f_1 = 1,\ f_2 = 1,\ f_3 = 2,\ f_4 = 3,\ f_5 = 5,\ f_6 = 8,\cr f_7 &= 13,\ f_8 = 21,\ f_9 = 34,\ f_{10} = 55,\ f_{11} = 89,\ f_{12} = 144}.$$ 

I observed that $f_3,\ f_6,\ 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,\ 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: 

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

$$\eqalign{ f_{4q+4} &= f_{4q+3} + f_{4q+2} = (f_{4q+2} + f_{4q+1}) + f_{4q+2} = 2f_{4q+2} + f_{4q+1} \cr &= 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_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.