Prove that among any 100 integers there are always two whose difference is divisible by...

kokomocutie88r1

kokomocutie88r1

Answered

2022-07-16

Prove that among any 100 integers there are always two whose difference is divisible by 99. How can I prove this?

Answer & Explanation

phravincegrln2

phravincegrln2

Expert

2022-07-17Added 19 answers

Step 1
Let r i 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.
Step 2
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.
phepafalowl

phepafalowl

Expert

2022-07-18Added 4 answers

Step 1
Here's a proof requiring no knowledge of division or remainders. Suppose a counterexample exists, i.e. there are 100 integers a 1 , , a 100 such that i j 99 a i a j . . Then they are distinct, so we may index them so that they're strictly ordered a 1 < a 2 < < a 100 . . Now if a 100 a 1 + 99 then by replacing a 100 by a 100 99 and reordering we obtain a new counterexample of smaller interval length ( = m a x m i n + 1), since the new sequence has the same min, by a 100 99 a 1 , , but has smaller max a 99 < a 100 , , and the new sequence remains a counterexample, since 99 a a 99 a ( a 99 ) . .
Step 2
Thus the least length counterexample must have length 99 , , hence its 100 integers all lie in the length 99 interval of consecutive integers a 1 , a 1 + 1 , , a 1 + 98. . Therefore, by the pigeonhole (box) principle, two of the integers are equal, a contradiction.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?