Suppose S is a set of n 1 integers Prove that there exist d

Suppose S is a set of n + 1 integers. Prove that there exist distinct a, b S such that a - b is a multiple of n.

Solution

There n distinct remainders modulo n ie 0,1,2,...,n-1

So let there be n boxes each corresponding to one of these remainders

We need to put these n+1 integers into these n boxes

So two of them must be in the same box ie two of them give the same remainder modulo n

Let those two integers be a,b

SO,a=b modulo n

a-b=0 modulo n

ie a-b is a multiple of n

HEnce proved