0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ This is not really a conjecture ; it is very well known and not hard at all to prove for mathematicians. :P $\endgroup$ – Patrick Da Silva Jun 15 '13 at 12:22
  • $\begingroup$ 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. $\endgroup$ – Carl Mummert Jun 15 '13 at 14:05
  • $\begingroup$ 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? $\endgroup$ – Carl Mummert Jun 15 '13 at 14:06
  • $\begingroup$ 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 $\endgroup$ – RZeta Jun 15 '13 at 14:33
3
$\begingroup$

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

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

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,

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.