Division Theorem/Proof 2

From ProofWiki
Jump to: navigation, search

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 < \left|{b}\right|$.

$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \left|{b}\right|$


Proof

Consider the set of integer multiples $x \, \left|{b}\right|$ of $\left|{b}\right|$ less than or equal to $a$:

$M := \left\{{k \in \Z: \exists x \in \Z: k = x \, \left|{b}\right|, k \le a}\right\}$

We have that:

$- \left|{a}\right| \, \left|{b}\right| \le - \left|{a}\right| \le a$

and so $M \ne \varnothing$.

From Set of Integers Bounded Above by Integer has Greatest Element, $M$ has a greatest element $h \, \left|{b}\right|$.

Then $h \, \left|{b}\right| \le a$ and so:

$a = h \, \left|{b}\right| + r$

where $r \ge 0$.

On the other hand:

$\left({h + 1}\right) \, \left|{b}\right| = h \, \left|{b}\right| + \left|{b}\right| > h \, \left|{b}\right|$

So:

$\left({h + 1}\right) \, \left|{b}\right| > a$

and:

$h \, \left|{b}\right| + \left|{b}\right| > h \, \left|{b}\right| + r$

Thus:

$r \le b$

Setting:

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

it follows that:

$h \, \left|{b}\right| = q b$

and so:

$a = q b + r$

as required.

$\blacksquare$


Sources