Proof of the Division Theorem (for all $a \in Z, b\in Z^+$, there exists $q,r\in Z$ such that $a=bq+r$ and $0\leq r\lt b$)

Question

I've been asked to prove the division theorem (for all $a \in Z, b\in Z^+$, there exists $q,r\in Z$ such that $a=bq+r$ and $0\leq r <b$). There are many proofs on SE, and the web, however I have been asked to prove the theorem using only the Ring Axioms of $Z$ and the Well-Ordering Principle (which is, as it turns out, rather tricky!). A proof, or even a few hints, would be very much appreciated.

Answer 1

First, do the case when $a\geq 0$. Let $S=\{n\in\mathbb{Z}\mid nb\gt a\}$. Show that $S$ is nonempty, and apply the well-ordering principle to $S$ to find its first element $p$. Then think about what the relationship between the $q$ you want and the $p$ you have might be.

Then, do the case $a\lt 0$ by applying the result to $a'=-a$ and leveraging that solution to find one for $a$.

Answer 2

Given $a \in \Bbb Z$ and $b \in \Bbb Z^{+}$.

The segment

$\quad [a,+\infty) = \{n \in \Bbb Z \mid a \le n\}$

is well-ordered.

Exercise 1: Prove that

$\tag 1 G = \bigr\{m \in \Bbb Z \mid (\exists\, q, r \in \Bbb Z)\; \bigr[ \,(m = bq + r) \, \land \, (a \le m) \, \land \, (0 \le r \lt b) \,\bigr] \bigr\}$

is non-empty (consider the number $b a^2$).

Since $G \subset [a,+\infty)$ let $\alpha = \text{min}(G)$.

Exercise 2: Prove that $a = \alpha$.