Show that among $n+1$ arbitrarily chosen integers, there must exist two whose difference is divisible by $n$.

When dividing by $n$, note that there are $n$ possible remainders*:   $0, 1, 2, \ldots, n-1$. These will play the role of our "pigeon-holes".

Taking as our "pigeons" the $n+1$ arbitrarily chosen integers -- by the pigeon hole principle, there must be two of these integers, say $a$ and $b$, that must have the same remainder, say $r$, upon division by $n$.

As such, we can find integers $k_1$ and $k_2$ such that

$$a = nk_1 + r \quad \textrm{ and } \quad b = nk_2 + r$$


$$a-b = nk_1 - nk_2 = n(k_1-k_2)$$

This implies $n \mid a-b$.

Hence, there must always exist two of our original $n+1$ numbers whose difference is divisible by $n$.


*Assuming remainders are found in the normal way -- as the positive values of magnitude less than $n$ that can be added to a multiple of $n$ to produce the number $n$ is dividing.