# 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):

- 2
- 89
- 1097
- 4513
- 13421
- 19801
- 93941
- 1 97273
- 5 75717
- 8 44117
- 122 39041
- 5550 03497
- 320 47071 64097
- 69771 47012 52068 98817
- 142 97347 97197 57578 00833
- 172 18960 63465 53144 12985 74525 96316 98569
- 1 33966 68724 91775 99369 69822 39683 40643 07947 19706 00954 57257
- 2083 37647 57839 72888 20735 84525 35988 93065 87989 74984 85114 54750 36495 64450 92274 33388 94573 31275 72413 09876 73858 32676 32450 35233 31957 84089 36148 70377 83820 03576 88501 89771 06846 88336 43637 53572 96135 36171 87210 31965 21080 43500 16127 13249