# How can I proceed in proving number theory/set exercise?

The problem states:

Prove that:

In every set of 100 integers, there exists two distinct integers x and y s.t. 89 | (x-y)

So far the only thing I've determined is that 89 is prime, so 89 | (x-y) if (x-y) = k*89 where k is an integer. I understand the statement, and I see how in every set of 100 integers, there will always exist an x and y s.t. (x-y) will be a multiple of 89, but how would I start formally proving this?

Any help would be appreciated.

-

Look at the congruence classes modulo $89$ i.e. any number can be written in the $$89m +k$$ for k $\in \{0,1,2,\ldots,88\}$. Now use Pigeonhole principle.