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 1 of 5: No term repeats

Previous step Next step

In plain words

If two terms were equal, they would trivially share a remainder, clashing with the hypothesis that early remainders are all different.

i<j,\ a_i=a_j\ \Longrightarrow\ \text{contradiction at }n=j

Detailed analysis

Suppose $a_i=a_j$ for some $i<j$ , and take $n=j$ . Among $a_1,\dots,a_n$ the hypothesis forces $n$ distinct remainders mod $n$ , but $a_i\equiv a_j\pmod n$ trivially since $a_i=a_j$ — a contradiction. So every integer appears in the sequence at most once.