Brazilian Mathematical Olympiad

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{aligned} 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{aligned}$$
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 \pmod{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{aligned} \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{aligned}$$
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.