Set of Successive Numbers contains Unique Multiple

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $m \in \Z_{\ge 1}$.

Then $\set {m, m + 1, \ldots, m + n - 1}$ contains a unique integer that is a multiple of $n$.

That is, in any set containing $n$ successive integers, $n$ divides exactly one of those integers.


Proof

Let $S_m = \set {m, m + 1, \ldots, m + n - 1}$ be a set containing $n$ successive integers.

The proof proceeds by induction on $m$, the smallest number in $S_m$.


Basis for the Induction

The case $m = 1$ is verified as follows:

$S_1 = \set {1, 2, \ldots, n}$

This contains a multiple of $n$, namely, $n$ itself.

If $S_1$ is a singleton then this element is trivially unique.

If there are any other integers in $S_1$, they are less than $n$ and more than $0$, and so cannot be a multiple of $n$.

This is the basis for the induction.


Induction Hypothesis

Fix $m \in \N$ with $m \ge 1$.

Assume that:

$S_m = \set {m, m + 1, \ldots, m + n - 1}$

contains a unique multiple of $n$.

This is our induction hypothesis.


Induction Step

This is our induction step:

Consider the set:

$S_{m + 1} = \set {m + 1, m + 2, \ldots, m + n - 1, m + n}$

As $n \equiv 0 \pmod n$, $m + n$ is a multiple of $n$ if and only if $m$ is a multiple of $n$.

That means that we can replace $m + n$ with $m$ and instead analyze:

${S_{m + 1} }' = \set {m + 1, m + 2, \ldots, m + n - 1, m}$


But ${S_{m + 1} }' = S_m$, which contains a unique multiple of $n$ by the induction hypothesis.

The result follows by the Principle of Mathematical Induction.

$\blacksquare$