IMO 1975 Problem 2
The statement concerns an arbitrary strictly increasing sequence of positive integers.
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 9m00s
Problem
Let $a_1, a_2, a_3, \cdots$ be an infinite increasing sequence of positive integers. Prove that for every $p \geq 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$.
Exploration
The statement concerns an arbitrary strictly increasing sequence of positive integers. Fixing an index $p$, we must show that infinitely many later terms of the sequence belong to the additive semigroup generated by $a_p$ and some larger term $a_q$.
A first attempt is to look at residues modulo $a_p$. Since the sequence is infinite, infinitely many terms must lie in the same residue class modulo $a_p$. Let that residue be $r$. If $a_q$ is one term in that class, then every later term in the same class satisfies
$$a_m-a_q\equiv 0 \pmod{a_p}.$$
Hence
$$a_m=a_q+x a_p$$
for some integer $x$. Because the sequence is increasing, $a_m>a_q$, so $x>0$. This already gives a representation
$$a_m=xa_p+1\cdot a_q.$$
The only issue is whether there are infinitely many terms in a single residue class. Since there are only $a_p$ residue classes modulo $a_p$ and infinitely many sequence terms, the pigeonhole principle gives exactly that.
Trying small examples confirms the idea. For $a_n=n$, fixing $p=3$ gives modulus $3$. Infinitely many terms are congruent to $1$ modulo $3$, namely $1,4,7,\ldots$. Choosing $a_q=4$, every later such term is of the form $4+3x$. For the sequence $a_n=2^n$, fixing $p=2$ gives modulus $4$. Infinitely many terms are congruent to $0$ modulo $4$. Choosing any later term $a_q$, every still later power of two differs from it by a multiple of $4$.
The crucial step is selecting a residue class containing infinitely many sequence terms and then fixing one element $a_q$ from that class. After that, every later element in the same class automatically yields the required representation with $y=1$.
Problem Understanding
We are given an infinite strictly increasing sequence of positive integers
$$a_1<a_2<a_3<\cdots.$$
For a fixed index $p\ge 1$, we must prove that infinitely many terms of the sequence can be expressed as
$$a_m=xa_p+ya_q,$$
where $x$ and $y$ are positive integers and $q>p$.
This is a Type B problem. The task is to prove a universal statement.
The objects involved are an increasing sequence of integers and representations of sequence terms as positive integer linear combinations of two selected sequence elements. The difficulty is that the sequence is completely arbitrary. No algebraic structure is assumed beyond strict increase. A direct attempt to construct representations from the values themselves appears impossible because the sequence may be highly irregular.
The central idea is that modulo $a_p$ there are only finitely many residue classes, whereas the sequence contains infinitely many terms. An infinite residue class then provides infinitely many differences divisible by $a_p$.
Proof Architecture
The proof uses two lemmas.
Lemma 1. Among the infinitely many terms $a_{p+1},a_{p+2},\ldots$, there exists a residue class modulo $a_p$ that contains infinitely many of them.
Sketch. There are only $a_p$ residue classes modulo $a_p$, so the pigeonhole principle forces one class to contain infinitely many terms.
Lemma 2. Let $a_q$ and $a_m$ belong to the same residue class modulo $a_p$ with $m>q$. Then
$$a_m=xa_p+a_q$$
for some positive integer $x$.
Sketch. Congruence gives divisibility of $a_m-a_q$ by $a_p$, and strict increase gives positivity of the quotient.
After proving these lemmas, choose an index $q>p$ from the infinite residue class supplied by Lemma 1. Every later term in that same class satisfies Lemma 2, yielding a representation with $y=1$. Since there are infinitely many such later terms, the theorem follows.
The most delicate point is ensuring that the coefficient of $a_p$ is positive rather than merely nonnegative. This requires using the strict increase of the sequence and the condition $m>q$.
Solution
Fix an arbitrary index $p\ge 1$.
Lemma 1
Among the terms
$$a_{p+1},a_{p+2},a_{p+3},\ldots,$$
there exists a residue class modulo $a_p$ containing infinitely many terms.
Proof
Modulo $a_p$ there are exactly $a_p$ residue classes:
$$0,1,\ldots,a_p-1.$$
Suppose that every residue class contained only finitely many terms of the set
$${a_{p+1},a_{p+2},a_{p+3},\ldots}.$$
Since there are only finitely many residue classes, the union of all these finitely many finite sets would be finite.
The set
$${a_{p+1},a_{p+2},a_{p+3},\ldots}$$
is infinite, which contradicts the preceding conclusion.
Hence at least one residue class modulo $a_p$ contains infinitely many terms of the sequence. ∎
Certification. This lemma establishes the existence of an infinite collection of sequence terms sharing a common residue modulo $a_p$; replacing this argument by a claim that such a class is merely nonempty would not be sufficient.
Lemma 2
Let $q>p$ and $m>q$. If
$$a_m\equiv a_q \pmod{a_p},$$
then
$$a_m=xa_p+a_q$$
for some positive integer $x$.
Proof
The congruence
$$a_m\equiv a_q \pmod{a_p}$$
means that
$$a_p\mid(a_m-a_q).$$
Therefore there exists an integer $x$ such that
$$a_m-a_q=xa_p.$$
Since the sequence is strictly increasing and $m>q$,
$$a_m>a_q.$$
Hence
$$a_m-a_q>0.$$
Because $a_p>0$, the equality
$$a_m-a_q=xa_p$$
implies
$$x>0.$$
Consequently,
$$a_m=xa_p+a_q,$$
with $x$ a positive integer. ∎
Certification. This lemma converts a congruence relation into the required representation; omitting the inequality $a_m>a_q$ would fail to justify that the coefficient $x$ is positive.
We now complete the proof.
By Lemma 1, there exists a residue class modulo $a_p$ containing infinitely many terms among
$$a_{p+1},a_{p+2},\ldots .$$
Choose an index $q>p$ such that $a_q$ belongs to this residue class.
Because the class contains infinitely many terms, there are infinitely many indices $m>q$ for which
$$a_m\equiv a_q \pmod{a_p}.$$
For each such $m$, Lemma 2 yields a positive integer $x$ satisfying
$$a_m=xa_p+a_q.$$
Writing
$$a_q=1\cdot a_q,$$
we obtain
$$a_m=xa_p+1\cdot a_q,$$
where both coefficients are positive integers and $q>p$.
Thus infinitely many terms $a_m$ admit a representation of the required form
$$a_m=xa_p+ya_q$$
with $x,y$ positive integers and $q>p$.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is Lemma 1. There are exactly $a_p$ residue classes modulo $a_p$. If each class contained only finitely many terms of the tail of the sequence, then the entire tail would be a finite union of finite sets and hence finite. The tail is infinite because the sequence itself is infinite. The contradiction forces at least one infinite residue class. A careless argument might say merely that two terms share a residue class, which does not provide infinitely many representations.
The second delicate step is the positivity of the coefficient $x$ in Lemma 2. From
$$a_m\equiv a_q \pmod{a_p}$$
one obtains
$$a_m-a_q=xa_p$$
for some integer $x$. The sign of $x$ is not determined by divisibility alone. The condition $m>q$ together with strict increase gives
$$a_m-a_q>0,$$
which forces $x>0$. Without strict increase, $x$ could be zero.
The third delicate step is fixing a single index $q$. The infinite residue class contains infinitely many indices. Choosing one of them as $q$, there remain infinitely many larger indices in the same class. Each larger index produces a representation with the same $q$. Choosing a different $q$ for each $m$ would not establish the statement as written.
Alternative Approaches
A different formulation uses the infinite pigeonhole principle directly. Consider the residues of all terms $a_n$ with $n>p$ modulo $a_p$. An infinite subset of indices has the same residue. Enumerate those indices as
$$n_1<n_2<n_3<\cdots.$$
For every $k\ge2$,
$$a_{n_k}-a_{n_1}$$
is a positive multiple of $a_p$, so
$$a_{n_k}=t_k a_p+a_{n_1}$$
with $t_k>0$. Taking $q=n_1$ immediately gives infinitely many desired terms.
Another approach introduces the equivalence relation
$$u\sim v \iff u\equiv v \pmod{a_p}$$
on the tail of the sequence. The tail is partitioned into finitely many equivalence classes. At least one class is infinite. Selecting the smallest-index element of that class as $a_q$, every other element of the class differs from it by a positive multiple of $a_p$, yielding the required representation. This is essentially the same argument expressed in the language of equivalence classes rather than residue classes.