Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
+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 – atb 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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