# Proving a statement using Pigeonhole principle

I am trying to understand how to prove a Statement using the pigeonhole principle.

Prove the following result using the pigeon-hole principle. In every collection of 7 integers there are at least two whose difference is divisible by 6. any ideas? thanks in advance

• Use the fact that for every $3$ consecutive integers, one will be divisible by $3$ and for every $2$ consecutive integers one will be even and divisible by $2$. Nov 29, 2017 at 14:28
• Hint: there are exactly $6$ possible remainders on division by six. If you have seven integers, then at least two have to have the same remainder.
– lulu
Nov 29, 2017 at 14:28

There are six possible remainders modulo 6: those are $0, 1, 2, 3, 4, 5$.
Since there are $7$ integers in your set, by the pigeonhole principle there will be at least two of them with the same remainder modulo 6. Their difference will then be divisible by $6$.
By the remainder's theorem, every integer number divided by $6$ is of the form: $$n=6q+r$$ where $0 \leq r < 6$
Since there are $6$ possible remainders, while you have $7$ numbers, at least two numbers must have the same remainder divided by $6$. Therefore, the difference of these two numbers must be divisible by $6$.