# 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:

1. Let $n \in \mathbb{N}$, $m \in \mathbb{N}^+$
2. Let $S = \{ s \in \mathbb{N} \; | \; \exists q \in \mathbb{N} \; (s = n - (q \times m)) \}$
3. We prove $S$ contains at least 1 natural number

1. We know $n = n - (0 \times m)$
2. Therefore $n \in S$
3. Therefore $S$ is not empty
4. We prove $S$ contains a smallest element

1. We know $S \subset \mathbb{N}$
2. We know $S$ is not empty (from 3)
3. Therefore $S$ contains a smallest element as $\mathbb{N}$ well ordered
5. Let $r$ be the smallest element in $S$

6. We know $\exists q \in \mathbb{N} \; (r = n - (q \times m))$ by dfn. of $S$
7. Therefore $n = (q \times m) + r$
8. We prove $r < m$

1. Lets assume $r \ge m$

1. $n - (q \times m) \ge m$
2. $n - (q \times m) -m \ge 0$
3. $n - ((q + 1) \times m) \ge 0$
4. $n - ((q+1) \times m) \in S$
5. $n - ((q+1) \times m) = r - m$
6. $n - ((q+1) \times m) < r$ (becos $m \in \mathbb{N}^+$)
7. $r$ is not the smallest element (contradiction)
2. $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?
-
Why is this so complicated? Suppose $n=qm+r$ and $r\geq q$. Redefine $r \rightarrow r-q$ and $m \rightarrow m+1$. Repeat until $r<q$. –  Douglas B. Staple Apr 10 '13 at 13:36

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].$

-

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

-