1
$\begingroup$

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.

1 Answers 1

5

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.

  • 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.2012-10-15