# division’s algorithm

let us write for the sake of young mathematicians this important arithmetic fact:

PROPOSITION:

$\forall a,b\in{\Bbb{Z}}\ \exists t,r\in{\Bbb{Z}}\ : a=bt+r,\quad 0\le r<|b|$

PROOF:

Let $a>b>0$ be the case and we set

$S_{ab}=\{a-bm\ge0\ |\ m\in{\Bbb{Z}}\}$

then there exists

$\exists$ $r=\min S_{ab}$.

If

$r=0$

then

$a=bt$.

For the rest of the argument we consider

$r>0$.

So

$r=a-bt,\qquad \exists t\in{\Bbb{Z}}$

and $a=bt+r$.

We are going to establish

$0\le r< b$.

Suppose

$r\ge b$

$r-b\ge0$

$0\le r-b

$0\le (a-bt)-b

if

$0

this contradicts the choice for   $r$

then

$0\le r

Now for uniqueness:

suppose

$a=bt+r,\qquad 0\le r

and

$a=bt'+r',\qquad 0\le r'

$r\ge r'$

$r-r'\ge 0$

but

$b(t'-t)=r-r'$ and

$b(t-t')=-r'+r>-r>-b$

are  integer multiples of $b$ between

$-b$ and $b$

then

$b(t-t')=0$

and

$t'-t=0$

since $b\neq0$.

So $t=t'$ and $r=r'$

$\Box$