Solution

Use the Euclidean Algorithm to find the greatest common divisor of the $12^{th}$ and $15^{th}$ Fibonacci numbers. For the purposes of counting, you may assume the first and second Fibonacci numbers are both equal to one.


Recall the Fibonacci numbers, $\{F_n\}$ are defined by the recursive relationship $F_{n+1} = F_n + F_{n-1}$ and $F_0 = F_1 = 1$. So the first few terms are:

$$1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,\ldots$$

The $12^{th}$ and $15^{th}$ values in this sequence are $144$ and $610$.

Using the Euclidean Algorithm to find their greatest common denominator, we discover

$$\begin{array}{rl} 610 &= 4 \cdot 144 + 34\\ 144 &= 4 \cdot 34 + 8\\ 34 &= 4 \cdot 8 + \fbox{2} \leftarrow gcd\\ 8 &= 4 \cdot 2 + 0 \end{array}$$