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

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?

• This is not really a conjecture ; it is very well known and not hard at all to prove for mathematicians. :P – Patrick Da Silva Jun 15 '13 at 12:22
• You should say "arbitrary numbers" instead of "random numbers". In the standard setting of probability there is no concept of a specific number being random. – Carl Mummert Jun 15 '13 at 14:05
• You left out two key things in the question: where did you encounter the question (what course, what textbook?) and more importantly: what did you already try? – Carl Mummert Jun 15 '13 at 14:06
• I came across a specific question during an interview ( Given 10 no.s p.t. difference of at least two must be divisible by 7 ) . I developed the above Q there after – RZeta Jun 15 '13 at 14:33

## 2 Answers

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

• Aww :P sorry I wrote the full answer. – Patrick Da Silva Jun 15 '13 at 12:22
• You are welcome @RZeta. – Abhra Abir Kundu Jun 15 '13 at 14:41

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,