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.

  • 1
    $\begingroup$ math.stackexchange.com/questions/594426/… $\endgroup$ – user8795 Jan 30 '18 at 1:39
  • 2
    $\begingroup$ If you have more pigeons than pigeon holes then one pigeon hole must have more than one pigeon. You have 8 numbers to place, and 7 pigeon holes to place them in. There must be two numbers in the same pigeon hole. If we subtract one of those numbers from its companion, the result will be divisible by 7. $\endgroup$ – Doug M Jan 30 '18 at 1:45

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.