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.

Respond to this Question

First Name
School Subject
Your Answer

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