XXVI OBM

Let's prove by induction that both $a_n$ is an integer and $\gcd (a_n,a_{n-1})=\gcd (a_n,a_{n-2})=\gcd (a_n,a_{n-3})=1$. It is certainly true for $n=3$ and direct substitutions show that it is true for $n\le 7$. Suppose that it's true for $n\le k$. First we prove that $a_{k+1}$ is an integer by showing that $a_{k-3}\mid a_k{a}_{k-2}+a_{k-1}^2$. In fact, $$\begin{array}{rl}{a}_{k-2}{a}_k+a_{k-1}^2& =\frac{a_{k-5}{a}_{k-3}+a_{k-4}^2}{a_{k-6}}\cdot \frac{a_{k-3}{a}_{k-1}+a_{k-2}^2}{a_{k-4}}+{\left(\frac{a_{k-4}{a}_{k-2}+a_{k-3}^2}{a_{k-5}}\right)}^2\\ & =\frac{a_{k-5}^2(a_{k-5}{a}_{k-3}+a_{k-4}^2)\cdot (a_{k-3}{a}_{k-1}+a_{k-2}^2)+a_{k-4}{a}_{k-6}(a_{k-4}{a}_{k-2}+a_{k-3}^2{)}^2}{a_{k-4}{a}_{k-6}{a}_{k-5}^2}\end{array}$$ Reducing modulo $a_{k-3}$ and noting that $\gcd (a_{k-3},a_{k-4})=\gcd (a_{k-3},a_{k-5})=\gcd (a_{k-3},a_{k-6})=1$ by induction hypothesis, this is equivalent to prove that $$a_{k-2}^2{a}_{k-4}^2(a_{k-5}^2+a_{k-4}{a}_{k-6})\equiv 0(\mathrm{mod}{a}_{k-3})$$ But $a_{k-5}^2+a_{k-4}{a}_{k-6}=a_{k-3}{a}_{k-7}$, so $a_{k-3}\mid a_k{a}_{k-2}+a_{k-1}^2$. Now the $\gcd$ part. Notice that $$\begin{array}{rl}\gcd (a_{k+1},a_k)& =\gcd \left(\frac{a_k{a}_{k-2}+a_{k-1}^2}{a_{k-4}},a_k\right)\\ & \le \gcd (a_k{a}_{k-2}+a_{k-1}^2,a_k)=\gcd (a_{k-1}^2,a_k)=1\end{array}$$ where the last equality follows from the induction hypothesis. The other equalities follow similarly: $$\gcd (a_{k+1},a_{k-1})\le \gcd (a_k{a}_{k-2}+a_{k-1}^2,a_{k-1})=\gcd (a_2{a}_{k-2},a_{k-1})=1$$ $$\gcd (a_{k+1},a_{k-2})\le \gcd (a_k{a}_{k-2}+a_{k-1}^2,a_{k-2})=\gcd (a_{k-1}^2,a_{k-1})=1$$ and the induction step is complete.