Problem 2

Let

a_1, a_2, a_3, \ldots

be an infinite increasing sequence of positive integers. Prove that for every

p \ge 1

there are infinitely many

a_m

which can be written in the form

a_m = xa_p + ya_q

with

x, y

positive integers and

q > p

Step 3 of 4: Turn the divisibility into the target linear form

Previous step Next step

a_{i_k}-a_q=k'a_p \implies a_{i_k}=k'a_p+1\cdot a_q,\quad k'\in\mathbb{Z}_{>0}

Detailed analysis

Fix any $k \ge 2$ and write $a_{i_k} - a_q = k'a_p$ for some integer $k'$ , using Step 2. Since the subsequence is strictly increasing, $a_{i_k} > a_q$ for $k \ge 2$ , so $k'a_p > 0$ and, as $a_p > 0$ , we get $k' > 0$ , i.e. $k'$ is a positive integer. Rearranging, $a_{i_k} = k' \cdot a_p + 1 \cdot a_q$ . This is exactly the target form $xa_p + ya_q$ with $x = k'$ and $y = 1$ , both positive integers, and with $q > p$ as required.