Saudi Arabian IMO Booklet

Consider any prime divisor $p$ of $a_n$. Consider a directed graph with $p$ edges on $\{0,1,\dots ,p-1\}$ (mod $p$) connecting $x\to y$ if and only if $$x^2+x-1\equiv y(\mathrm{mod}p).$$ Observe that $\frac{p-1}{2}$ is connected to $b=\frac{p^2-5}{4}$ (mod $p$), every element has out-degree 1, and every element other than $b$ has in-degree 2 or 0, elements $\pm 1$ form loops, $-2\to 1$ and $0\to -1$. If we have a path $a_0\to a_1\to \cdots \to a_n$, then each of the elements has in-degree two, with at least one having in-degree one, giving $2n-1$ edges in total. Counting the four extra edges above, we deduce that $p\ge 2n+3$, which implies that $\gcd (a_n,2n+1)=1$. $\square$