Posted by **thisha** on Wednesday, November 29, 2006 at 10:27pm.

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.

- discrete math -
**MathMate**, Monday, May 9, 2011 at 5:29pm
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.

## Answer this Question

## Related Questions

- Math - How many integers between 200 and 500 inclusive leave a remainder 1 when ...
- Math - How many integers bewteen 200 and 500 inclusive leave a remainder 1 when ...
- Math - When 14 is divided by 5, the remainder is 4. When 14 is divided by a ...
- Math - When 17 is divided by k,where k is a positive integer less than 17,,the ...
- math, algebra - 2a+2ab+2b I need a lot of help in this one. it says find two ...
- math - You are given a positive integer such that when the integer is divided by...
- Discrete Math - Let n be positive integer greater than 1. We call n prime if the...
- math - what is the least common positive integer that meets the following ...
- discrete math - Could someone help me with this induction proof. I know its true...
- math - what is the least common positive integer that meets the following ...

More Related Questions