MAS114: Challenge Problem 4

Problem

The \emph{Fibonacci numbers} are a function \(F:\bN\rightarrow\bN\) defined by \(F(0) = 0\), \(F(1) = 1\), and \(F(n) = F(n-1) + F(n-2)\) for \(n\geq 2\). So, for example, \(F(2) = 1\), \(F(3) = 2\), \(F(4)=3\), \(F(5)=5\), and so on.

Is $F(2013)$ even or odd? Find an odd prime factor of \(F(2013)\).

Solution

A good number of people (Martha Ball, Oliver Feghali, Issy Frankel, James Kirke, James Mason, Mateusz Szwedowicz, Xhoi Xhetani) spotted that the Fibonacci numbers cycle between odd, odd and even numbers, with \(F(0), F(3), F(6), \ldots\) even, and so \(F(2013)\) is even: 2013 is a multiple of three.

Ben Andrews and Francisco Melo Parente also conjectured that if \(m\) divides \(n\), then \(F(m)\) divides \(F(n)\), and that since 2013 is a multiple of 11, \(F(2013)\) should be a multiple of \(F(11)=89\). This turns out to be true, and is a little fiddly to prove. It's not very hard to prove this special case by hand — the sequence \(F(n)\) has period only 44 modulo 89, and there are shortcuts one can take in finding this — but nobody did so.

Knowing that, and equipped with a modern computer algebra package, it is possible to give a full prime factorisation of \(F(2013)\). The factors consist of the following primes (once each):