Set of Successive Numbers contains Unique Multiple

From ProofWiki
Jump to navigation Jump to search


This article has been identified as a candidate for Featured Proof status.
If you do not believe that this proof is worthy of being a Featured Proof, please state your reasons on the talk page.
To discuss this page in more detail, feel free to use the talk page.


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


This article contains statements that are justified by handwavery.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding precise reasons why such statements hold.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Handwaving}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


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$

Retrieved from "https://proofwiki.org/w/index.php?title=Set_of_Successive_Numbers_contains_Unique_Multiple&oldid=401262"