2
$\begingroup$

Show that of any $m$ consecutive integers, exactly one is divisible by $m$. I am finding it difficult to prove that there is only one number among $m$ consecutive integers that is divisible by $m$.

$\endgroup$
1
$\begingroup$

Let the numbers be $b_r=a+r, 0\le r\le m-1$

Existence:

We can apply Pigeonhole Principle to prove the existence by contradiction.

Let none of them is divisible by $m,$ so they can leave $m-1$ distinct remainder$(r)$s namely, $1\le r\le m-1$

But, as there are $m$ numbers, so at least tow of them leave the same remainders.

Let $b_u,b_v$ leave the same remainders where $1\le u<v\le m-1$

Then $m$ divides $b_v-b_u=v-u$

But, $0<v-u<m-1$ can not be divisible by $m$

Uniqueness:

If $m$ divides both $b_s,b_t,0\le s\le t\le m-1$

$m$ must divide $b_t-b_s=t-s$ which lies $\in(0,m-1]$ which is impossible

So, there can be at most one $r$ divisible by $m$

$\endgroup$
  • $\begingroup$ Did you prove existence? Or just uniqueness? $\endgroup$ – Zubin Mukerjee Nov 27 '14 at 8:21
  • $\begingroup$ @ZubinMukerjee, Updated. Thanks for your observation $\endgroup$ – lab bhattacharjee Nov 27 '14 at 8:25
  • $\begingroup$ I don't think it's actually the pigeonhole principle, since there are $m$ things in $m$ boxes (as opposed to $m+1$ things in $m$ boxes) and we're trying to show that each box has one thing (instead of at least one box having two things). $\endgroup$ – Zubin Mukerjee Nov 27 '14 at 8:25
  • 1
    $\begingroup$ @ZubinMukerjee, Let none of them is divisible by $m$. Then there can be $m-1$ distinct remainders $1\cdots m-1$ by $m$ $b_r$s $\endgroup$ – lab bhattacharjee Nov 27 '14 at 8:26
  • $\begingroup$ Okay, you should add this to the answer, +1 $\endgroup$ – Zubin Mukerjee Nov 27 '14 at 8:27
1
$\begingroup$

Hints:

Any integer can be written one of $m$ numbers: $km,km+1,\cdots, km+(m-1)$

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