Library / Chinese Mathematical Olympiad /2 of 17

Chinese Mathematical Olympiad

Number theory Difficulty 5.3 AIME, harder Prove it China

Given an integer $k \ge 3$ and a sequence $\{a_n\}$ that satisfies $a_k = 2k$ and for each $n > k$ ,
$a_n = \begin{cases} a_{n-1} + 1, & \text{if } a_{n-1} \text{ and } n \text{ are coprime,} \\ 2n, & \text{otherwise.} \end{cases}$
Prove that $a_n - a_{n-1}$ is a prime for infinitely many $n$ . (Posed by Zhu Huawei)

Solution

Suppose that $a_l = 2l$ , $l \ge k$ . Let $p$ be the least prime divisor of $k-1$ . Then $(l-1, i) = \begin{cases} 1, & 1 \le i < p, \\ p, & i = p, \end{cases}$ and thus
$(2l + i - 2, l + i - 1) = \begin{cases} 1, & 1 \le i < p, \\ p, & i = p. \end{cases}$
From (1) we know that
$a_{l+i-1} = \begin{cases} 2l + i - 1, & 1 \le i < p, \\ 2l + 2p - 2, & i = p. \end{cases}$
Then $a_{l+p-1} - a_{l+p-2} = (2l+2p-2) - (2l+p-2) = p$ is a prime number, $a_{l+p-1} = 2(l+p-1)$ . From the discussion above, we know that there are infinitely many $l \ge k$ , such that $a_l = 2l$ and $a_{l+p-1} - a_{l+p-2} = p$ is the least prime divisor of $l-1$ .

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.