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
@J.D. Obviously $n\mid 0$. –  Martin Sleziak Apr 1 '12 at 4:40
@MartinSleziak silly me! –  user2468 Apr 1 '12 at 4:54

5 Answers 5

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

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

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


share|improve this answer

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

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

Your Answer


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.