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

Question

What are the pigeons and the pigeonholes and how to prove this statements?

At first I tried to the following:

There are "100 choose 2" or 4950 pairs of integers. But I don't know how to move further. Or if we consider the min element of the set. There are 99 pairs with the min integer in the pair. So there are at least 99 unique differencies. Don't know how it helps either.

Answer 1

This is already true for every set of 38 integers. Just pack these integers into the 37 boxes corresponding to remainder modulo $37$.

Answer 2

The pigeons are the 100 integers. The pigeonholes are the numbers 0 to 36. Map integer k to rem(k, 37). Since there are 100 pigeons and only 37 pigeonholes, two pigeons must go in the same pigeonhole. This means rem(k1, 37) = rem(k2, 37,), which implies that k1 − k2 is a multiple of 37.