AoPS - Problem

Source: Turkey National MO 2024 P3

Tags: number theory

egxa

17.12.2024 10:41

For all $n\ge2$ positive integer, let $f(n)$ denote the product of all distinct prime divisors of $n$. For example, $f(5)=5$, $f(8)=2$, and $f(12)=6$. Given a sequence ${a_n}$, where $a_1\ge2$, defined as follows: $$a_{n+1}=a_n+f(a_n)$$ Show that for any prime $p$, there exists a term $a_k$ in the sequence such that $p|a_k$.

Let $a_n=f(a_n).b_n$. Let $b_m$ be the minimum term in the sequence ${b_n}$. $b_m$ will increase by one $t$ times until there is a prime $q$ doesn't divide $f(a_m)$ and divides $b_{m+t}$. (Note that $t\leq q-1$) $b_{m+t}\leq \frac{b_m+t}{q}\leq \frac{b_m+q-1}{q}$ so $q.b_m\leq q.b_{m+t} \leq b_m+q-1$ therefore $b_m=1$. Then it can be seen that the sequence $b$ will increase to least prime that doesn't divide at least one term of the sequence and falls back to $1$. As conclusion every prime divides at least one term of the sequence. $\blacksquare$