Ask questions and get helpful answers.

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.

  1. 👍
  2. 👎
  3. 👁
  4. ℹ️
  5. 🚩

1 answer

  1. 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.

    1. 👍
    2. 👎
    3. ℹ️
    4. 🚩

Answer this Question

Related Questions

Still need help?

You can ask a new question or browse existing questions.