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.
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.
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!
Submit Your Answer
We prioritize human answers over AI answers.
If you are human, and you can answer this question, please submit your answer.