The proof given for the statement
$$\exists \: q, \, r \in \mathbb{N} \; (n = q \times m + r \wedge r < m)$$
looks like:
- Let $n \in \mathbb{N}$, $m \in \mathbb{N}^+$
- Let $S = \{ s \in \mathbb{N} \; | \; \exists q \in \mathbb{N} \; (s = n - (q \times m)) \}$
We prove $S$ contains at least 1 natural number
- We know $n = n - (0 \times m)$
- Therefore $n \in S$
- Therefore $S$ is not empty
We prove $S$ contains a smallest element
- We know $S \subset \mathbb{N}$
- We know $S$ is not empty (from 3)
- Therefore $S$ contains a smallest element as $\mathbb{N}$ well ordered
Let $r$ be the smallest element in $S$
- We know $\exists q \in \mathbb{N} \; (r = n - (q \times m))$ by dfn. of $S$
- Therefore $n = (q \times m) + r$
We prove $r < m$
Lets assume $r \ge m$
- $n - (q \times m) \ge m$
- $n - (q \times m) -m \ge 0$
- $n - ((q + 1) \times m) \ge 0$
- $n - ((q+1) \times m) \in S$
- $n - ((q+1) \times m) = r - m$
- $n - ((q+1) \times m) < r$ (becos $m \in \mathbb{N}^+$)
- $r$ is not the smallest element (contradiction)
- $r < m$
A few questions
- Is $S$ the set of possible remainders? If so, how can the divined ($n$) be in the set of possible remainders?
- Why might $r$ be the smallest element in $S$?
- Can someone explain the rationale behind steps 8.1.2 - 8.1.5?