MathLabs

Problem 2

Let a1,a2,…a_1, a_2, \dots be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer nn the numbers a1,a2,…,ana_1, a_2, \dots, a_n leave nn different remainders upon division by nn. Prove that every integer occurs exactly once in the sequence.
Step 4 of 5: Infinitely many signs force infinite growth
Previous stepNext step
In plain words

A block that only ever grows by one integer at a time cannot contain infinitely many positive and infinitely many negative terms unless it keeps extending in both directions forever.

n→∞ ⟹ {a1,…,an} grows without bound in both directionsn\to\infty\ \Longrightarrow\ \{a_1,\dots,a_n\}\ \text{grows without bound in both directions}
Detailed analysis

By the previous step, at every stage {a1,…,an}\{a_1,\dots,a_n\} is a block of nn consecutive integers that grows by exactly one integer, on the left or the right, as nn increases by 11. Since the full sequence has infinitely many positive terms and infinitely many negative terms, this block must extend infinitely far in both directions as n→∞n\to\infty.