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 1 of 4: Fix

p

and look at remainders modulo

a_p

Previous step Next step

In plain words

There are only $a_p$ possible remainders when dividing by $a_p$ (namely $0, 1, \ldots, a_p-1$ ), but infinitely many terms in the sequence beyond position $p$ . Like the pigeonhole principle with infinitely many pigeons and finitely many holes, some remainder must be hit infinitely often — and any two terms sharing that remainder differ by a multiple of $a_p$ , which is exactly the kind of structure the target formula $xa_p+ya_q$ needs.

a_1<a_2<a_3<\cdots,\quad p\ge 1 \text{ fixed}

Detailed analysis

Fix $p \ge 1$ . For each index $i$ , let $r_i$ be the remainder of $a_i$ upon division by $a_p$ , so $r_i \in \{0, 1, \ldots, a_p - 1\}$ : only $a_p$ possible values. Since the sequence $a_1, a_2, a_3, \ldots$ is infinite, the pigeonhole principle guarantees that at least one remainder $r$ occurs for infinitely many indices $i$ .