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.
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.
To solve this problem, we can make use of the Pigeonhole Principle. The Pigeonhole Principle states that if you have more pigeons than pigeonholes, then at least one pigeonhole must contain more than one pigeon.
In this case, the pigeons represent the d+1 integers and the pigeonholes represent the d possible remainders when the integers are divided by d.
Since we have d+1 integers and only d possible remainders, by the Pigeonhole Principle, there must be at least two integers that have the same remainder when divided by d.
To prove this formally, let's assume that all d+1 integers have distinct remainders. This means that each pigeonhole contains only one pigeon. However, this would imply that there are more pigeonholes (d) than pigeons (d+1), which contradicts the Pigeonhole Principle.
Therefore, our assumption must be false, and there must be at least two integers with exactly the same remainder when divided by d among any group of d+1 integers, not necessarily consecutive.
To prove that among any group of d+19 integers, there are two with exactly the same remainder when divided by d, we can use the Pigeonhole Principle.
The Pigeonhole Principle states that if n pigeons are placed in m pigeonholes and n > m, then at least one pigeonhole must contain more than one pigeon.
In this case, the "pigeons" are the d+19 integers and the "pigeonholes" are the possible remainders when dividing by d.
Since there are d possible remainders (0, 1, 2, ..., d-1), and we have d+19 integers, by the Pigeonhole Principle, at least two of the integers must have the same remainder when divided by d.
Therefore, among any group of d+19 integers, there are always two with exactly the same remainder when they are divided by d.