Problem 2

Let

a_1, a_2, \dots

be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer

n

the numbers

a_1, a_2, \dots, a_n

leave

n

different remainders upon division by

n

. Prove that every integer occurs exactly once in the sequence.

Step 2 of 5: Consecutive-index terms stay close

Previous step Next step

In plain words

If two early terms were far apart, that very distance would be small enough to serve as an $n$ in which they collide.

i<j\ \Longrightarrow\ |a_i-a_j|<j

Detailed analysis

Suppose $|a_i-a_j|\ge j$ for some $i<j$ , and set $n=|a_i-a_j|\ne0$ (nonzero by the previous step). Then $i<j\le n$ , so both indices lie in $[1,n]$ , and $a_i\equiv a_j\pmod n$ by construction of $n$ — contradicting that $a_1,\dots,a_n$ have $n$ distinct remainders mod $n$ . Hence $|a_i-a_j|<j$ whenever $i<j$ .