Given n numbers, prove that difference of at least one pair of these numbers is divisible by n-1

Question

Suppose you have a list of $n$ numbers, $n\geq 2$. Let $A$ be the set of differences of pairs of the $n$ numbers. Prove or disprove that at least one element of A must be divisible by $n-1$.

Anyone come across this conjecture before? Could someone provide a proof?

Answer 1

Hint:The remainders of any number on division by $n-1$ are $0,1,2,\dots ,n-2$($n-1$ possibilities)

Solution:

As there are $n-1$ possible remainders so among $n$ numbers there must be at least two having the same remainder on division bu $n-1$. The difference of these two numbers must be divisible by $n-1$.

Answer 2

Since you have $n$ numbers, at least two of them must be congruent modulo $n-1$ because there are only $n-1$ equivalence classes $\pmod{n-1}$ (pigeonhole principle). If $a \equiv b \pmod{n-1}$, then $n-1$ divides $a-b$.

Hope that helps,