how to prove using pigeonhole principle there exist two of them, $a_i$ and $a_j$, such that $$ divides $a_i − a_j$.

Question

Let $a_1,a_2,\cdots, a_{n+1}$ be $ + 1$ distinct positive integers, show that there exist two of them, $a_i$ and $a_j$, such that $$ divides $a_i − a_j$.How to solve this using pigeon hole principle?

Answer 1

We prove the stronger: Namely this statement but for $n$ integers than $n$+$1$.

Assume all of the integers are distinct (mod $n$) so that we don't have simple trivial cases such as $a_i$=$0$(mod $n$). Then there are $n$-$1$ remainders (excluding $0$). So we have by the pigeonhole principle, there must be two integers with the same remainder, say $a_i$ and $a_j$. In other words, $a_i=a_j$(mod $n$), which would imply the given result.

Since it holds for $n$ numbers, it must hold for $n$+$1$ numbers.