Perhaps we consider the remainders of the members of the sequence after we divide by n. The only possible values for remainders are less than n and greater than 1 (otherwise, we'd be done), and we have n numbers, so at least two members of the sequence have the same remainder.