For all $m,n \in \Bbb{N}$, $n>m$, there is a unique $k \in \Bbb{N}$ such that $km \le n < (k+1)m$

Question

For all $m,n \in \Bbb{N}$, $n>m$, there is a unique $k \in \Bbb{N}$ such that $km \le n < (k+1)m$

My attemt for existence (is this approach correct?)

Let $m,n \in \Bbb{N}$ and consider the set $S = \{q \in \Bbb{N} | qm \le n \}$

Since $1 \in S$, $S$ is nonempty, so by the Well Ordering Principle there is a least element $k \in S$.

Then, suppose $(k+1)m \le n$

Then $km \le n - m = 0$, which is absurd, as $km \in \mathbb{N}$. So $n < (k+1)m$ and then $km \le n < (k+1)m$.

Is this correct?

For the uniqueness, I'm stuck. I tried supposing there are different $k,k'$ and using the two inequalities for each, but can't get to a contradiction...

Answer 1

I believe you need the greatest $k\in S$. Try, for instance, $n=5$, $m=1$. Then the smallest element in $S$ is $k=0$ and ... you see where this is going. Fortunately, you can show that $S$ is bounded, and hence that it achieves a maximum. This is also a consequence of the well ordering principle. The fact that $S$ is bounded means $\mathbb{N}-S$ is non-empty. The maximum of $S$ is one less than the minimum of $\mathbb{N}-S$.

If $k$ is the max, then $k+1$ is not in $S$ by definition. Note that this approach kind of hints at the uniqueness argument ... what's wrong with choosing a different $k$? Can you take it from here / fill in the uncited principles?

Edit: Also, $n-m>0$.

Edit: I am adding some comments on uniqueness. For $k=max(S)$, $k+1\in \mathbb{N}-S$ by definition. Therefore, $(k+1)m\leq n$ is not true, and the negation of that inequality is $n< (k+1)m$. So, in this situation, $km\leq n<(k+1)m$.

If we choose $k$ such that $k>max(S)$, then we lose the $km\leq n$ since $k$ is not in $S$.

If we choose $k$ such that $k<max(S)$, then $k+1\leq max(S)$ and $$(k+1)m\leq max(S)m\leq n$$ and we lose $n<(k+1)m$.

Does this help?

Answer 2

You were on the right track in your last sentence.

"For the uniqueness, I'm stuck. I tried supposing there are different $k,k′$ and using the two inequalities for each, but can't get to a contradiction..."

Ok, so suppose $k \neq k'$. Then we may assume without loss of generality that $k < k',\ $ and so $\exists i \in \mathbb{N}$ such that $k' = k+i$. So:

$(1) \quad km \leq n < (k+1)m,\ $ and

$(2) \quad (k+i)m \leq n < (k+i+1)m . $

Taking $m(i-1)$ away from $(2)$ gives:

$(2b) \quad (k+1)m \leq n+(1-i)m < (k+2)m$.

Putting $(1)$ and $(2b)$ together:

$km \leq n < (k+1)m \leq n+(1-i)m \leq n,\quad$ since $1-i \leq 0$.

This says that $n<n$ which is impossible.

Therefore, our assumption that $k \neq k'$ has lead to a contradiction: this proves uniqueness.