1.26 Theorem

1.26 Theorem Prove the existence part of the Division Algorithm.

The Theorem

Let $n$ and $m$ be natural numbers. Then (existence part)
there exists integers $q$ (for quotient) and $r$ (for remainder) such that

$$\begin{align} \ m & = nq +r \notag \\ \end{align}$$

and $0 \le r \le n-1.$ Moreover (uniqueness part), if $q$, $q'$, and $r$, $r'$ are integers that satisfy

$$\begin{align} \ m & = nq +r \notag \\ & = nq' +r' \notag \\ \end{align}$$

with $0 \le r, r' \le n-1$, then $q = q'$ and $r= r'$.

Attempted Proof

Let $S$ be the set of natural numbers $ni$, where $i$ is a natural number such that $ni > m$. By the Well-Ordering Axiom, $S$ has a smallest a smallest element, call it $nj$.

$$\begin{align} nj - m & \le n && \text{else } n(j-1) \text{ would be a smaller element} \notag \\ n \underbrace{(j-1)} _q & \le m \notag \\ \end{align}$$

Since $n(j-1) \le m$ there must exist an integer $r$ such that

$$\begin{align} n \underbrace{(j-1)} _q + r & = m && \text{given } 0 \le r \notag \\ \end{align}$$

if $r$ were $\ge n$ then there would exist a natural number $z$ such that $r = n + z$

$$\begin{align} n \underbrace{(j-1)} _q + n + z & = m && \text{given } 0 \le r \notag \\ nj + z & = m && \text{given } 0 \le r \notag \\ nj &\ge m && \text{given } 0 \le r \notag \\ nj \ge m \land nj &< m && \text{given } 0 \le r \notag \\ false \notag \\ \end{align}$$

So we have that $r < n$.

$$\begin{align} n \underbrace{(j-1)} _q + r & = m && \text{given } 0 \le r \le n-1 \notag \\ \end{align}$$

Let $q$ be the integer $j-1$, and we get

$$\begin{align} nq + r & = m && \text{given } 0 \le r \le n-1 \notag \\ \end{align}$$
$\Box$