Use pigeonhole principle to show that one of any n consecutive integers divisible by n?

Answer 1

Let's look at a simple example first such as 3 consecutive integers. We want to show that it is divisible by 3.

Take 4,5, and 6 and of course 6 is divisible by 3.
The reason for this is can be seen using the pigeonhole principle.

When an integer is divided by 3, possible remainders are 0, 1, and 2. It follows that every
integer can be expressed in one of the forms 3k, 3k + 1, and 3k + 2 where k is an integer.
So if we have any three consecutive integers, one of them must be divisible by 3.


Let's look at how the pigeonhole principle applies. Suppose we have 3 consecutive integers are non are divisible by 3. Think of the pigeon holes as 3k, 3k + 1, and 3k + 2, now this means no numbers are in the 3k hole and two of them must be in either the 3k+1 hole or the 3k+2 hole. But this contradicts that they are consecutive integers.


So for any n, let the pigeon holes be nk, nk+1,... nk+(n-1) and these exhaust the multiples of n. Now if you take n consecutive numbers, you must have a least 1 number in the nk pigeon hole or else they are not consecutive.