Let $(a_n)$ be the integer sequence which is defined by $a_1= 1$ and $$ a_{n+1}=a_n^2 + n \cdot a_n \,\, , \,\, \forall n \ge 1.$$Let $S$ be the set of all primes $p$ such that there exists an index $i$ such that $p|a_i$. Prove that the set $S$ is an infinite set and it is not equal to the set of all primes.
Problem
Source: 2022 Saudi Arabia IMO TST 1.1
Tags: number theory, divides, number theory with sequences, recurrence relation
02.11.2022 00:38
$S$ isn't the set of all primes: $a_{3i+1} \equiv 1 \pmod{3}$, $a_{3i+2} \equiv 2 \pmod{3}$ and $a_{3i+3} \equiv 2 \pmod{3}$. Therefore, $3$ isn't in $S$. $S$ is infinite because $a_{n+1} = a_n(a_n + n)$. Take $n = 3p$ with $p$ a prime. If $p | a_{3p} \hspace{0.25cm} \forall p$ prime, then the set is obviously infinite. If $p \nmid a_{3p}$ for a certain $p$, then there will be a prime $q$ with the property that $q|a_{3p+1}$ and $q\nmid a_{3p}$ making it an infinite set. Proof: $a_{3p+1} = a_{3p}(a_{3p} + 3p)$. We have $gcd(a_{3p},(a_{3p}+3p) = gcd(a_{3p},3p)$ and as $3p \nmid a_{3p}$, we have $gcd(a_{3p}, 3p) = 1$ meaning $a_{3p+1}$ has (atleast) one prime factor more than $a_{3p}$ had, making it an infinite set.
03.11.2022 02:44
Assume that $S$ is finite. since if $p|a_i \Rightarrow p|a_j$ for all $j \ge i$ and $a_{n+1}=a_n(a_n+n)$, after some point $a_n+n$ stops making "new" primes, but since any $a_n$ has finite number of prime divisors, and $n$ varies by natural numbers, by Kobayashi's theorem $\{a_n+n \}$ have infinitely many prime divisors, hence contradiction, therefore $S$ is Infinite @Below I think it is fine to quote it without proof
04.11.2022 02:58
Woah, Kobayashi's theorem is so powerful! Thanks for introducing me to something new xd. Is this allowed to quote in international contests (as I feel like the proof must be super complex!)?
02.06.2024 12:50
When the first part is a cakewalk but you miscalculate $a_5$ so you don't get the second part Part 1 ($S$ is infinite): Assume otherwise and say $S = \{p_1, p_2, \cdots, p_k \}$. Then there exists $m$ with $p_i \mid a_m \forall i = 1, 2, \cdots, k$. Now choose $b = a_{hp_1p_2\cdots p_k + 1}$ with $hp_1p_2\cdots p_k + 1 > m$. then $a_{hp_1p_2\cdots p_k + 2} = b(b+hp_1p_2\cdots p_k + 1)$. But $b+hp_1p_2\cdots p_k + 1$ is coprime to each of the $p_i$ and isn't $1$, so there exists a new prime dividing $a_{hp_1p_2\cdots p_k + 2}$, contradiction. $\square$ Part 2 ($S$ isn't the set of all primes): We claim that $3 \notin S$. Indeed, if $a_{3i+1} \equiv 1 \pmod{3}, a_{3i+2} \equiv 2 \pmod{3}, a_{3i+3} \equiv 2 \pmod{3}, a_{3i+4} \equiv 1 \pmod{3}$. But $a_1 \equiv 1 \pmod{3}$, SO $3 \nmid a_i \forall i $ .$\square$