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.

-
+1 , Marvelous! –  Salech Alhasov Oct 15 '12 at 4:48
I want to also give a +1, but I need more reputation, so thanks for the help! I'll give it a try –  alexthebake Oct 15 '12 at 4:51
alex, you may not be able to vote, but if you decide this answer suits you, you can (and you are encouraged to) accept it by clicking the check mark next to it. –  Gerry Myerson Oct 15 '12 at 4:53