Proof of remainder always less than divisor 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? 

 A: In a loose sense $S$ is the set of possible remainders: it’s the set of amounts by which $n$ differs from a multiple of $m$. That is, you look at all possible multiples $qm$ of $m$ (for $q\in\Bbb N$) and see how much $n$ differs from each of them; those differences are the members of $S$. As a result $S$ contains the non-negative numbers in the following list:
$$\begin{align*}
&n-0\cdot m=n\;,\\
&n-1\cdot m=n-m\;,\\
&n-2\cdot m=n-2m\;,\\
&n-3\cdot m=n-3m\;,\\
&\qquad\qquad\;\,\vdots
\end{align*}\tag{1}$$
Remember, we’re looking for natural numbers $q$ and $r$ such that $n=qm+r$, which means that $r=n-qm$; thus, if such $q$ and $r$ exist, the remainder $r$ must be one of the numbers in the list $(1)$. We also want $r$ to be non-negative, so $r$ will actually be in $S$ and not just in the list $(1)$.
We know that $n\in\Bbb N$, so we know that the list $(1)$ does have at least one non-negative member, and therefore $S\ne\varnothing$. You ask how $n$ can be a candidate for the remainder: what if $m>n$? What if, for instance, $m=5$ and $n=3$? Then dividing $n$ by $m$ yields a quotient $q=0$ and a remainder $r=n=3$: $3=0\cdot 5+3$.

Why might $r$ be the smallest element of $S$?

I’m not sure what you’re asking here. In the proof we simply let $r$ be the smallest element of $S$ and then prove that this number has the desired properties. Are you asking why we might think of trying this value of $r$? We already know that the remainder has to be in $S$, and we also know that it has to be less than $m$, so we want it to be small rather than large; it makes sense, therefore, to try the smallest member of $S$ to see whether it does the job.
The argument in step 8 is by contradiction: we suppose that $r\ge m$ and derive a contradiction, so that we can conclude that $r<m$, just as we want. Recall that $r$ is the smallest member of $S$ and that $q$ has been chosen so that $n=qm+r$. Thus, $n-qm=r$, and since we’ve assumed that $r\ge m$, this implies that $n-qm\ge m$. Subtract $m$ from both sides of the inequality to get $n-qm-m\ge 0$, and then combine the two $m$ terms to get $n-(q+1)m\ge 0$. Now $q\in\Bbb N$, so $q+1\in\Bbb N$, and therefore $n-(q+1)m$ is one of the numbers in the list $(1)$. For convenience let $s=n-(q+1)m$; as we just saw, $s$ is in the list $(1)$. Moreover, we just showed that $s\ge 0$, so $s$ is actually in $S$. (Recall that $S$ is the set of non-negative members of the list $(1)$.)
But if you look back at the algebra that we just did, you can see that $$s=n-(q+1)m=(n-qm)-m=r-m\;.$$ Now recall that by hypothesis $m\in\Bbb N^+$, so $m>0$, and therefore $s=r-m<r$. In other words, $s$ is a member of $S$ that’s smaller than $r$, contradicting our choice of $r$ as the smallest member of $S$. This contradiction shows that $r$ cannot be greater than or equal to $m$ and hence that $r<m$.
A: Hint $\,\ $ The idea is this: $ $ the least natural  $\rm\: r\in  \bar S = n\!-\!m\,\Bbb N\ $ satisfies $\rm\ r < m,\ $ since otherwise $\rm\:r\ge m\ $ so $\rm\ r\!-\!m\ge 0 \:$ is a smaller natural in $\rm\,\bar S,\:$ by $\rm\:r = n\!-\!mq\:$ $\Rightarrow$ $\rm\:r\!-\!m = n\!-\!m(q\!+\!1)\in\bar S.$ 
Said dynamically: if you repeatedly subtract $\rm\:m\:$ from $\rm\:n\:$ you eventually reach an $\rm\, r\in [0,m\!-\!1].$
