Saudi Arabian IMO Booklet

First, we shall show that $3\notin S$ by proving that $$a_{3k-2}\equiv 2(\mathrm{mod}3),a_{3k-1}\equiv 2(\mathrm{mod}3)\text{ and }{a}_{3k}\equiv 2(\mathrm{mod}3).$$ Since $a_1=1$, $a_2=2$, $a_3=2^2+2\cdot 2=8\equiv 2(\mathrm{mod}3)$ so the claim is true for $k=1$. Suppose that the claim holds for $k=n$. We have $$\begin{array}{rl}{a}_{3n+1}& =a_{3n}(a_{3n}+3n)\equiv 2\cdot 2\equiv 1(\mathrm{mod}3),\\ a_{3n+2}& =a_{3n+1}(a_{3n+1}+3n+1)\equiv 1(1+1)\equiv 2(\mathrm{mod}3),\\ a_{3n+3}& =a_{3n+2}(a_{3n+2}+3n+2)\equiv 2(2+2)\equiv 2(\mathrm{mod}3).\end{array}$$ 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^{\prime }}$ for all $t^{\prime }\ge t$. Similarly for $p_2,p_3,\dots ,p_k$ so there exist $N$ big enough such that $p_1{p}_2\cdots p_k|a_n$ for all $n\ge N$. Taking the integer $\ell >N+1$ such that $\ell \equiv 2(\mathrm{mod}{p}_1{p}_2\cdots p_k)$. Since $a_{\ell }=a_{\ell -1}(a_{\ell -1}+\ell -1)$, we get $$a_{\ell -1}+\ell -1\equiv 1(\mathrm{mod}{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$