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 2 of 4: Pick the infinite subsequence sharing that remainder

Previous step Next step

a_{i_1}<a_{i_2}<a_{i_3}<\cdots,\quad a_{i_k}\equiv r \pmod{a_p}

Detailed analysis

Let $a_{i_1} < a_{i_2} < a_{i_3} < \cdots$ be the (infinite) subsequence of all terms with $a_{i_k} \equiv r \pmod{a_p}$ . Because the original sequence is infinite, we may discard finitely many terms and assume every index $i_k$ satisfies $i_k > p$ ; set $q = i_1$ , so $q > p$ . Every term $a_{i_k}$ with $k \ge 2$ now satisfies $a_{i_k} \equiv a_q \equiv r \pmod{a_p}$ , so $a_p \mid (a_{i_k} - a_q)$ .