Show that for every set of 18 integers there will be two that are divisible by 17

Question

I understand the pigeonhole principle is needed here and I see the solution in the back of the book, but the explanation is week. If anyone could explain step-by-step that would be awesome!

Answer 1

Assuming the problem as it is currently written is written incorrectly and that the intended problem is the following:

Given a set of $18$ integers $x_1,x_2,\dots,x_{18}$, there will exist two integers $x_i, x_j$ with $1\leq i<j\leq 18$ such that $x_i-x_j$ is divisible by $17$.

By the quotient remainder theorem, each of the integers $x_i$ can be written in a unique way as $17q_i+r_i$ where $q_i$ and $r_i$ are both integers and $0\leq r_i<17$. We treat the values of $r_i$ as the holes and the elements in our set as the pigeons. There are then $17$ holes and $18$ pigeons.

By the pigeon-hole principle, there must be two terms with the same remainder. Without loss of generality, suppose that it was $x_i$ and $x_j$ where $x_i=17q_i+r$ and $x_j=17q_j+r$. Then $x_i-x_j = 17q_i+r-17q_j-r = 17(q_i-q_j)$ is therefore divisible by $17$.

---

The way it is currently worded (Show that for every set of 18 integers there will be two that are divisible by 17) is false. We can have a set of $18$ integers such that none of them are divisible by $17$, for example the set $\{1,2,3,4,\dots,16,18,19\}$.

Even if we were to add additional constraints that each of the integers is consecutive, we have the counterexample $\{1,2,3,\dots,18\}$ has exactly one element divisible by $17$, not two.