2005 IMO Shortlist Problems/N2
Problem
Let be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer
the numbers
leave
different remainders upon division by
.
Prove that every integer occurs exactly once in the sequence .
Solution
It is clear that if and only if
, or the sequence would not satisfy the specified property.
If , then
and
leave the same remainder when divided by
, which violates the given condition for the sequence when
. It then follows that
for all positive integers
and
. Now consider
, and let this be
, with
. It follows that
are all in the closed interval
, and hence
is a permutation of
consecutive numbers, for all
.
Note that there are infinitely many positive and negative terms. Therefore for any arbitrarily large integer there exists an
such that
and a
such that
. Since
is a permutation of
consecutive integers, it follows that every integer in the range
is in the sequence, and consequently every integer occurs in the sequence.