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 \pmod{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 \dots \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$