Problem

Source: RMO Delhi 2016, P2

Tags: number theory, greatest common divisor



Consider a sequence $(a_k)_{k \ge 1}$ of natural numbers defined as follows: $a_1=a$ and $a_2=b$ with $a,b>1$ and $\gcd(a,b)=1$ and for all $k>0$, $a_{k+2}=a_{k+1}+a_k$. Prove that for all natural numbers $n$ and $k$, $\gcd(a_n,a_{n+k}) <\frac{a_k}{2}$.