discrete math
posted 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, ...d1. So there are a total of d different remainders, but you have d + 1 numbers.

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.
Respond to this Question
Similar Questions

math, algebra
2a+2ab+2b I need a lot of help in this one. it says find two consecutive positive integers such that the sum of their square is 85. how would i do this one i have no clue i know what are positive integers.but i don't know how to figure … 
discrete math
Could someone help me with this induction proof. I know its true. given then any integer m is less than or equal to 2, is it possible to find a sequence of m1 consecutive positive integers none of which is prime? 
math
What is the lowest numberthat has a remainder of 1 when divided by 2 and a remainder of 2 when devided by 3 and a remainder of 3 when divided by 4 and a remainder of 4 when divided by 5? 
math
what is the least common positive integer that meets the following conditions: divided by 7 with remainder 4 divided by 8 with remainder 5 divided by 9 with remainder 6 i thought you could add 7 and 4 to get 13, then divide 13 and … 
math
You are given a positive integer such that when the integer is divided by 1995, the remainder is 75. What will the remainder be when the same positive integer is divided by 57? 
Math
When 17 is divided by k,where k is a positive integer less than 17,,the remainder is 3.What is the remainder when the sum of the possible values of k is divided by 17? 
Math
How many integers bewteen 200 and 500 inclusive leave a remainder 1 when divided by 7 and a remainder 3 when divided by 4? 
Math
How many integers between 200 and 500 inclusive leave a remainder 1 when divided by 7 and a remainder 3 when divided by 4? 
Discrete Math
Let n be positive integer greater than 1. We call n prime if the only positive integers that (exactly) divide n are 1 and n itself. For example, the first seven primes are 2, 3, 5, 7, 11, 13 and 17. (We should learn more about primes … 
Math
When 14 is divided by 5, the remainder is 4. When 14 is divided by a positive integer n, the remainder is 2. For how many different values of n is this possible. Is listing it out the only way?