Just as the title says, Prove that any collection of $8$ distinct integers contains distinct $x$ and $y$ such that $x - y$ is divisible by $7$.
I have seen a couple of questions here that are almost identical to this question but all of the answer for them are very brief so I was not able to fully understand how to do this question. I have an answer key and it says the following:
Pigeonholes : $0,1,\dots, 6$ ( all possible remainders after division by $7$)
Pigeons : $8$ distinct integers
As you can tell it's quite brief for an answer key. I was wondering if someone could explain to me how to use Pigeonhole principle here to get the answer in a little more detail.
Each of the $8$ selected integers has a remainder on division by $7$.
As there are only $7$ possible values for the remainders, (at least) two of the integers must have the same remainder, by the pigeonhole principle.
So we can pick two integers $a,b$ from the $8$ that have the same remainder, say $r$, meaning that we can write $a=7j+r$ and $b=7k+r$ for some integer values of $j$ and $k$.
Then $a-b = (7j+r)-(7k+r) = 7j-7k = 7(j-k)$
So $a{-}b$ is divisible by $7$ as required.