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.