Post a New Question

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 -

    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

First Name:
School Subject:

Related Questions

More Related Questions

Post a New Question