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.
Solution 1:
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$.
Is $m+c$ one of the $n$ consecutive integers? In other words, is it true that $0\le c<n$?
Is $m+c$ divisible by $n$? Why?
Solution 2:
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}$.
Clarification: Let $C_k=\{k+j:0\le j\lt n\}$ be a set of $n$ consecutive integers.
Proposition 1: No two distinct elements of $C_k$ can be in the same residue class mod $n$.
Suppose otherwise: $j_1\lt j_2$ and $$ k+j_1\equiv k+j_2\pmod{n}\tag1 $$ Then $$ j_2-j_1\equiv0\pmod{n}\tag2 $$ which is impossible since $\color{#C00}{j_1\lt j_2}$ and $\color{#090}{k+j_1,k+j_2\in C_k}$ imply $$ 0\color{#C00}{\lt}j_2-j_1\color{#090}{\lt}n\tag3 $$ Proposition 2: For any $m$ some element of $C_k$ is $m\pmod{n}$.
Suppose otherwise: $C_k$ is a subset of the $n-1$ residue classes mod $n$ that are not $m\pmod{n}$. The Pigeonhole Principle says that two elements of $C_k$ must be in the same residue class mod $n$, which Proposition 1 says is impossible.
Solution 3:
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\}. $$
Base case: $P(1)$ is trivial since $n \in \{1, 2, \ldots, n\}.$
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}$
-
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.