Question

Let d be a positive integer. Show that among any group of d+ 1 (not necessarily consecutive) integers there are two with exactly the same remainder when they are divided by d.

Answer 1

When an integer is divided by d the possible remainders are {0, 1, 2, ..., d–1}.

The possible number of remainders is d, or $|\{0, 1, 2, ..., d–1\}|=d$ .

By the Pigeonhole Principle:

objects = umber of integers = d+1

holes = number of remainders = d

$\lceil\frac{d+1}{d}\rceil=2$

So by the Pigeonhole Principle, among any group of d+1 integers there are two with exactly the same remainder when divided by d.