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

Question

The possible values of the remainders are 0, 1, 2, ...d-1. So there are a total of d different remainders, but you have d + 1 numbers.

Answer 1

cont'd
So by the Pigeon hole theorem, there are at least two numbers with the same remainders when divided by d.

Note: four and a half years too late, but someone searching for the Pigeon hole theorem may find it useful.