Problem 1465

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_1a_2a_3\dots a_{n-1} - 1 \ge a_1a_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_1a_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 \pmod{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 \pmod{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 \pmod{p}$ for some $n \ge 2$. Then $a_{n+1} = a_n^2 + a_n - 1 \equiv 1^2 + 1 - 1 \equiv 1 \pmod{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 \pmod{p}$ and $a_k \equiv -1 \pmod{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{aligned} 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{aligned}$$
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 \pmod{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.