Prove that among any 100 integers there are always two whose difference is divisible by...
Prove that among any 100 integers there are always two whose difference is divisible by 99. How can I prove this?
Answer & Explanation
Let be the remainder when the i-th integer in our list is divided by 99.
There are only 99 conceivable remainders, the numbers 0 to 98.
Since there are 100 integers in our list, and only 99 conceivable remainders, there must be two different numbers in our list which have the same remainder. This is a consequence of the Pigeonhole Principle, but the fact is clear even without a name for it.
Finally, if two numbers have the same remainder on division by 99, their difference is divisible by 99.
Here's a proof requiring no knowledge of division or remainders. Suppose a counterexample exists, i.e. there are 100 integers such that . Then they are distinct, so we may index them so that they're strictly ordered . Now if then by replacing by and reordering we obtain a new counterexample of smaller interval length (), since the new sequence has the same min, by , but has smaller max , and the new sequence remains a counterexample, since .
Thus the least length counterexample must have length , hence its 100 integers all lie in the length 99 interval of consecutive integers . Therefore, by the pigeonhole (box) principle, two of the integers are equal, a contradiction.