Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|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 –  alexthebake Oct 15 '12 at 4:51
2  
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
add comment

Your Answer

 
discard

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.