In every set of 100 integers, there exist two whose difference is a multiple of 37.

Question

Could anyone explain how to prove this? There are 4950 ways in which a difference between two integers from the set can be taken. I cannot understand how to relate it with a multiple of 37.

Answer 1

For every integer in the set, take the remainder of the division by 37: there are only 37 possibile different results. Let $a$ and $b$ two integers of the set which have the same remainder, i.e:

$$ \begin{align*} a &= r + 37h,\\ b &= r + 37k. \end{align*} $$

Now consider the difference $a - b = 37(h-k)$: it is a multiple of 37.