Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|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

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=qn+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|cite|improve this answer
Please forgive my asking, but did you mean to write $m=qn+r$ (where $0 \le r <n$) in your division equation? Otherwise I don't see how $q$ and $r$ are the quotient and remainder when you divide $m$ by $n$. – EthanAlvaree Apr 16 '15 at 13:17
@EthanAlvaree: Thanks. Yes, that second $m$ was a typo. ($0<r$ is right, though.) – Brian M. Scott Apr 16 '15 at 15:09

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