# Prove that one of $n$ consecutive integers must be divisible by $n$

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

-
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?

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

QED.

-

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

-

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

-

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

\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} $$\implies n!|k(k-1)(k-2)....(k-(n-1))$$ $$\implies n|k(k-1)(k-2)....(k-(n-1))$$

-
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