Proof of the division algorithm

Question

I wasn't happy with the proof provided by the book, so I had an attempt at it, but I don't know if it's right. The theorem is:

Let $a,b\in\mathbb{Z}$ and $b\neq0$. Then there exist unique $m,r\in\mathbb{Z}$ such that $a=mb+r$ and $0\leq r< |b|$.

I'm not going to attempt uniqueness here, and also just refer to the case for $a\geq 0, b>0$.

Suppose b|a. Then by definition, $\exists m$ such that $a=mb$. Then choose $r=0$ and the result is proved.

Suppose $b\nmid a$. Then $\exists m$ such that $\textrm{gcd}(a,mb)=1$ and $a-b <mb<a$. Then choose $r=a-mb$. Since $r=||a|-|mb||<|a-(a-b)|=b$ by the triangle inequality, then $0<r<b$, and the result is proved.

Answer 1

Suppose $b\nmid a$. Then $\exists m$ such that $\textrm{gcd}(a,mb)=1$ is a wrong assumption.

Take $a=4$ and $b=6$. $4$ does not divide $6$. However you can't find $m$ such that $\textrm{gcd}(4,m6)=1$.

Answer 2

This classical result is proved in many algebra and number theory books. There are two proofs for the division theorem, online available at Poroofwiki. Both use that Integers bounded above have a greatest element.

Answer 3

Algorithmically:

Set $m, r:= 0,a$. Then, as long as $r\ge b$, perform $m, r:=m+1,r-b$.

At any time, $a=mb+r$ holds, and when the iterations stop, $\color{green}{a=mb+r\land0\le r<b}$.

The iterations are guaranteed to stop, as $m\ge a$ yields $r=a-mb=a-ab\le0<b$.

---

Uniqueness is not very difficult.

Let $a=m'b+r'$ with $0\le r'<b$ and $a=m''b+r''$ with $0\le r''<b$.

Then by subtraction $(m'-m'')b+(r'-r'')=0$ so that $r'-r''$ is a multiple of $b$. This multiple cannot be other than $0$, as $|r'-r''|<b$. And $r'=r''$ implies $m'=m''$.