Saudi Arabian IMO Booklet

First, we shall show that $3 \notin S$ by proving that
$$a_{3k-2} \equiv 2 \pmod{3},\ a_{3k-1} \equiv 2 \pmod{3}\ \text{ and }\ a_{3k} \equiv 2 \pmod{3}.$$
Since $a_1 = 1$, $a_2 = 2$, $a_3 = 2^2 + 2 \cdot 2 = 8 \equiv 2 \pmod{3}$ so the claim is true for $k = 1$.
Suppose that the claim holds for $k = n$. We have
$$\begin{align*} a_{3n+1} &= a_{3n}(a_{3n} + 3n) \equiv 2 \cdot 2 \equiv 1 \pmod{3}, \\ a_{3n+2} &= a_{3n+1}(a_{3n+1} + 3n + 1) \equiv 1(1 + 1) \equiv 2 \pmod{3}, \\ a_{3n+3} &= a_{3n+2}(a_{3n+2} + 3n + 2) \equiv 2(2 + 2) \equiv 2 \pmod{3}. \end{align*}$$
Thus, the claim is also true for $k = n + 1$. So by induction, the claim is proved.

Now suppose on the contrary that $S$ is finite, denote $S = \{p_1, p_2, \dots, p_k\}$. Note that $a_n|a_{n+1}$ so $a_n|a_m$ for all $m \ge n$. By the definition of $S$, there are some index $t$ such that $p_1|a_t$, thus $p_1|a_{t'}$ for all $t' \ge t$. Similarly for $p_2, p_3, \dots, p_k$ so there exist $N$ big enough such that $p_1p_2\cdots p_k|a_n$ for all $n \ge N$. Taking the integer $\ell > N + 1$ such that $\ell \equiv 2 \pmod{p_1p_2\cdots p_k}$. Since $a_\ell = a_{\ell-1}(a_{\ell-1} + \ell - 1)$, we get
$$a_{\ell-1} + \ell - 1 \equiv 1 \pmod{p_1 p_2 \cdots p_k}$$
so $a_{\ell-1} + \ell - 1$ is coprime to all primes in $S$, which implies that $S$ has some prime divisor that not belong to $S$, a contradiction. Hence, $S$ is an infinite set. $\square$