posted by thisha on .
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.
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.
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.