# Discrete Math - Counting

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

• Hint: Pigeon hole principle. – Deven Ware Nov 13 '12 at 5:51

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$.

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$.

Hint:

$99 \mid (a-b)$ if and only if $a \equiv b \pmod{99}$.

Here's a proof requiring no knowledge of division or remainders. Suppose a counterexample exists, i.e. there are $100$ integers $\rm\:a_1,\ldots, a_{100}\:$ such that $\rm\:i\ne j\:\Rightarrow\:99\nmid a_i-a_j.\:$ Then they are distinct, so we may index them so that they're strictly ordered $\rm\:a_1 < a_2 < \ldots < a_{100}.\:$ Now if $\rm\:a_{100} \ge a_1\! + 99\:$ then by replacing $\rm\:a_{100}\:$ by $\rm\:a_{100}-99\:$ and reordering we obtain a new counterexample of smaller interval length (= max - min+$1$), since the new sequence has the same min, by $\rm\:a_{100}\!-99 \ge a_1,\:$ but has smaller max $\rm a_{99} < a_{100},\:$ and the new sequence remains a counterexample, since $\:\rm\:99\mid a'\!-\!a\iff 99\mid a'\!-(a\!-\!99).\:$ Thus the least length counterexample must have length $\le 99,\:$ hence its $100$ integers all lie in the length $99$ interval of consecutive integers $\rm\:a_1, a_1\!+\!1,\ldots, a_1\!+\!98.\:$ Therefore, by the pigeonhole (box) principle, two of the integers are equal, a contradiction.

Remark $\$ The proof exploits the fact that the $99$ integers $\rm\:a_1,\, a_1\!+\!1,\ldots, a_1\!+\!98\:$ form a complete system of representatives for remainders (congruence classes) modulo $99$. By modifying the proof to also allow replacing the min element by $\pm 99$ we can shift the representatives to any sequence of $99$ consectutive integers, e.g. the standard choice $\:0,1,\ldots,98\:$ employed in the other proofs. Then it is clear how the proof is related to the other proofs: instead of working on one integer at a time, repeatedly adding or subtracting $99$ to get its remainder into the standard range, the proof instead spreads out these operations, reordering them so that each step forces the extreme elements closer to the sought range. So the proof essentially "inlines" the algorithm of division with remainder. Conceptually a proof that explicitly uses congruence classes is superior, since it provides some conceptual (arithmetical) meaning to the boxes employed in the box principle.