Asked by thisha

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.

Answers

Answered by MathMate
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.
There are no AI answers yet. The ability to request AI answers is coming soon!

Related Questions