Division Theorem/Proof 2

From ProofWiki
Jump to navigation Jump to search


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

From Set of Integers Bounded Above by Integer has Greatest Element, $M$ has a greatest element $h \size b$.

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$


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


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


$r \le b$


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