72nd Czech and Slovak Mathematical Olympiad

a) By mathematical induction, we first prove that $a_n\ge 2$ for every $n$. For $n=1$ and $n=2$ this is true because $a_1=3$ and $a_2=2$. Now suppose that for some $n\ge 3$ the inequality $a_k\ge 2$ holds for every $k<n$. Then we have $a_n=a_1{a}_2{a}_3\dots a_{n-1}-1\ge a_1{a}_2-1=5$, so indeed $a_n\ge 2$.

Let us now show that numbers $a_n$ are pairwise coprime. Indeed, for any two indices $k<n$ we have $a_k\mid a_1{a}_2\dots a_{n-1}=a_n+1$, whence for the largest common divisor $D$ of the numbers $a_n$ and $a_k$ we get $D\mid a_n$ and at the same time $D\mid a_n+1$ (because $D\mid a_k$ and $a_k\mid a_n+1$), so necessarily $D=1$, so $a_n$ and $a_k$ are coprime. Due to $a_n\ge 2$ we find for each index $n$ a prime number, denote it by $p_n$, for which $p_n\mid a_n$. Since all $a_n$ are pairwise coprime, the prime numbers $p_n$ are pairwise different. Thus a) is proved.

b) If $n\ge 2$, then $a_{n+1}=a_1{a}_2{a}_3\dots a_{n-1}{a}_n-1=(a_n+1)a_n-1=a_n^2+a_n-1$. Next we work with this expression.

Assume that $p\mid a_n$ for some $n\ge 2$ and for some prime $p$. Then $a_{n+1}=a_n^2+a_n-1\equiv -1(\mathrm{mod}p)$. From here we get for the next member $a_{n+2}=a_{n+1}^2+a_{n+1}-1\equiv (-1{)}^2+(-1)-1\equiv -1(\mathrm{mod}p)$, and so, by mathematical induction, all members $a_k$ with indices $k\ge n+1$ give the same remainder $p-1$ modulo $p$. If the assumption $p\mid a_n$ is satisfied for some $n\ge 2$, we call the prime $p$ bad. Our task is actually to find infinitely many primes $p\ge 5$ that are not bad (we impose the condition $p\ge 5$ so that $p\mid a_1=3$ does not hold).

Let us now consider a prime $p$ satisfying $a_n\equiv 1(\mathrm{mod}p)$ for some $n\ge 2$. Then $a_{n+1}=a_n^2+a_n-1\equiv 1^2+1-1\equiv 1(\mathrm{mod}p)$, so using mathematical induction, we get that all numbers $a_k$ with indices $k\ge n$ give a remainder 1 when dividing by $p$. Then let us call such $p$ good. Note that no prime $p\ge 5$ is good and bad at the same time—because it is not possible that for sufficiently large $k$ both relations $a_k\equiv 1(\mathrm{mod}p)$ and $a_k\equiv -1(\mathrm{mod}p)$ hold. Therefore it is enough to prove that there are infinitely many good primes.

To find good primes we use the sequence $(b_n{)}_{n=1}^{\infty }$ given by the formula $b_n=a_n-1$ for each $n\ge 1$. It is obvious that $b_1=2$, $b_2=1$ and $$\begin{array}{rl}{b}_{n+1}& =a_{n+1}-1=(a_n^2+a_n-1)-1=((b_n+1{)}^2+(b_n+1)-1)-1=\\ & =b_n^2+3b_n=b_n(b_n+3)\end{array}$$ for every $n\ge 2$. Then a prime number $p$ is good if and only if $p\mid b_n$ for some $n\ge 2$. We thus reached a situation similar to that in part a)—we need to prove existence of infinitely many primes dividing at least one member of the new sequence $(b_n{)}_{n=2}^{\infty }$ determined by its first term $b_2=1$ and the relation $b_{n+1}=b_n(b_n+3)$ for each $n\ge 2$.

We begin with an observation that $b_k\mid b_n$ if $2\le k\le n$. Indeed from $b_{k+1}=b_k(b_k+3)$ we have $b_k\mid b_{k+1}$ and further by induction $b_k\mid b_n$ for every $n\ge k$.

We now prove that, under the assumption $2\le k<n$, the numbers $b_k+3$ and $b_n+3$ are coprime. Indeed, their greatest common divisor $D$ satisfies $D\mid b_k+3\mid b_{k+1}\mid b_n$ and at the same time $D\mid b_n+3$, so together $D\mid (b_n+3)-b_n=3$ and therefore either $D=1$ or $D=3$. It remains to exclude the value $D=3$: due to $b_2=1$ and the relationship $b_{n+1}=b_n(b_n+3)$ it follows by an easy induction $b_n\equiv 1(\mathrm{mod}3)$ for each $n\ge 2$. So, $3\nmid b_n$, and therefore also $3\nmid b_n+3$, and thus $D\ne 3$.

Finally, we know that $b_n\ge 1$ for every $n$ (since $a_n\ge 2$), and thus $b_n+3\ge 4$. Therefore, for each $n$ we find a prime number $p_n$ with the property $p_n\mid b_n+3$. All these prime numbers $p_n$ are according to the previous paragraph different from each other, in addition from $b_n+3\mid b_{n+1}$ follows $p_n\mid b_{n+1}$ for every $n\ge 2$. So we have found an infinite sequence of prime numbers dividing at least one member of the sequence $(b_n{)}_{n=2}^{\infty }$. The proof of part b) is complete.