Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If we have $n$ consecutive integers, then one of these integers is divisible by $n$. Prove the above statement.

share|improve this question
    
Do you mean consecutive non-zero integers? Since, for example, there is no $x \in \{0, 1, \ldots, n-1 \}$ such that $n \mid x.$ –  user2468 Apr 1 '12 at 4:27
7  
@J.D. Obviously $n\mid 0$. –  Martin Sleziak Apr 1 '12 at 4:40
1  
@MartinSleziak silly me! –  user2468 Apr 1 '12 at 4:54
add comment

5 Answers

HINTS: Let the integers be $m,m+1,\dots,m+n-1$. If $m$ is a multiple of $n$, you’re done. If not, write $m=qm+r$, where $q$ and $r$ are integers, and $0<r<n$. Here $q$ and $r$ are just the quotient and remainder when you divide $m$ by $n$. Let $c=n-r$.

  1. Is $m+c$ one of the $n$ consecutive integers? In other words, is it true that $0\le c<n$?

  2. Is $m+c$ divisible by $n$? Why?

share|improve this answer
add comment

There are $n$ residue classes mod $n$. If you have $n$ consecutive integers, they will fill up all $n$ residue classes. One of them must be in the residue class of things divisible by $n$; i.e. things $=0\pmod{n}$.

share|improve this answer
add comment

Proof by induction.

For all $i \in \mathbb{N}_{\ge 1},$ let $P(i)$ be the proposition: $$ \exists q \in \mathbb{N}_{\ge 1} \text{ such that } qn \in \{i, i+1, \ldots, i+n-1\}. $$

  1. Base case: $P(1)$ is trivial since $n \in \{1, 2, \ldots, n\}.$

  2. Induction hypothesis: Assume $P(i)$ holds for some $i > 1.$ In other words, there exists some $q$ such that $qn \in \{i, i+1, \ldots, i+n-1 \} \tag{1}$

  3. Induction step: Consider the set $\{i+1, i+2, \ldots, i+n \}.$ The induction hypothesis in equation $(1)$ implies two cases:

    Case I: $i \neq qn,$ i.e. $qn \in \{i+1, \ldots, i+n-1\}.$ Hence $qn \in \{i+1, i+2, \ldots, i+n \}.$ So $P(i+1)$ holds.

    Case II: $i = qn,$ and hence $i+n = n(q+1).$ Since $i+n \in \{i+1, i+2, \ldots, i+n \},$ we have that $P(i+1)$ holds.

    We have just shown that $P(i) \implies P(i+1).$

QED.

share|improve this answer
add comment

Hint $\ $ Let $\rm\ a\ $ be the largest in the sequence. $\rm\: mod\ n\!:\ a\equiv r\,\in\, [\:\!0,\:\!n)\:$ so $\rm\:n\ |\ a\!-\!r\,\in\, [\!\:a,\:\!a\!-\!n)$

This has widespread applications, e.g. this proof that $\rm\:n\:|\:(n\!-\!1)!\:$ for composite $\rm\:n.$

Note $\ $ This is just a shifted equivalent of the Division Algorithm, i.e. the following equivalence is true in any euclidean domain $\rm Z\:$ (domain with an algorithm for division with 'smaller' remainder)

$$\begin{array}{rcrlrl} &\rm \exists\!\!\!&\rm q,r \in Z, &\rm\ a\: =\: q\:n + r, \!\!\!\!&\rm |r| \!\!\!&\rm <\ |n| \\ \displaystyle\rm{b\: =\: a\!-\!r\ \atop{\huge\iff\atop\phantom{M}}} &\rm \exists\!\!\! &\rm q,b\in Z, &\rm\ b\: =\: q\:n, \!\!\!\!&\rm |a\!-\!b| \!\!\!&\rm <\ |n| \end{array}\qquad$$

share|improve this answer
add comment

$\ let \ k,k-1,k-2,....,(k-(n-1)) \ are \ 'n' \ consecutive \ integers.$

$\begin{equation} \begin{aligned} k(k-1)(k-2)(k-3).....(k-(n-1))=& \frac{k(k-1)(k-2)(k-3).....(k-(n-1))(k-n)....1}{(k-n).....1}\\ =&{\frac{k!}{(k-n)!n!}.n!}\\ \end{aligned} \end{equation}$ $$\implies n!|k(k-1)(k-2)....(k-(n-1))$$ $$\implies n|k(k-1)(k-2)....(k-(n-1))$$

share|improve this answer
    
This is incomplete/wrong. For instance $4$ divides $6 \times 2$, but does not divide either $6$ or $2$. –  Aryabhata Apr 6 '12 at 8:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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