Question

If d is a positive integer, how many integers must we divide by d to guarantee that two of them leave the same remainder? Explain your answer.

Answer 1

When any integer is divided by d, there are d possible remainders, namely the integers 0, 1, 2, ... ,d − 1.

Now the pigeonhole principle states that if n items are put into m containers, with n>m, then at least one container must contain more than one item.

So by the Pigeonhole Principle, some remainder must be hit twice if we have at least d + 1 integers.

Hence we have to choose at least d+1 integers to guarantee that two of them leave the same remainder when divided by d.