# discrete math

posted by .

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 -

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.

## Similar Questions

1. ### 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 …
2. ### 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 m-1 consecutive positive integers none of which is prime?
3. ### 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?
4. ### 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 …
5. ### 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?
6. ### 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?
7. ### 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?
8. ### 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?
9. ### 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 …
10. ### 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?

More Similar Questions