Should I really compute that monster?

Number Theory Level 3

Let $F_n$ denote the $n^\text{th}$ Fibonacci number .

Compute $\gcd(F_{2000}F_{16} + F_{1999}F_{15}, F_{1014}F_{1001} + F_{1013}F_{1000})$ .

Notation : $\gcd(a,b)$ denotes greatest common divisor of $a$ and $b$ .

1 solution

Brian Riccardi
Feb 14, 2016

It can be proved this property of Fibonacci numbers

$F_{n+m} = F_{n}F_{m} + F_{n-1}F_{m-1}$ $\forall n,m \in \mathbb{N_0}$

So the problem asks to compute $gcd(F_{2016},F_{2015})$

A well known fact is that consecutive Fibonacci numbers are coprime and then the answer is $\boxed{1}$