Division Theorem/Proof 2

Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:

$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Consider the set of integer multiples $x \size b$ of $\size b$ less than or equal to $a$:

$M := \set {k \in \Z: \exists x \in \Z: k = x \size b, k \le a}$

We have that:

$-\size a \size b \le -\size a \le a$

and so $M \ne \O$.

Then $h \size b \le a$ and so:

$a = h \size b + r$

where $r \ge 0$.

On the other hand:

$\paren {h + 1} \size b = h \size b + \size b > h \size b$

So:

$\paren {h + 1} \size b > a$

and:

$h \size b + \size b > h \size b + r$

Thus:

$r \le b$

Setting:

$q = h$ when $b > 0$

$q = -h$ when $b < 0$

it follows that:

$h \size b = q b$

and so:

$a = q b + r$

as required.

$\blacksquare$