# Proof of the division algorithm

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.

• why such an $m$ exists, for example for $a=6,b=4$? – Ofir Schnabel Aug 12 '15 at 13:02
• Could I say, instead, choose $m$ such that $m=\mathrm{max}\{x:x\in\mathbb{N}\cup\{0\}\;\;\; \mathrm{and}\;\;\; mx< a\}$? – George Aug 12 '15 at 13:09
• I think you should use the classic proof. – Ofir Schnabel Aug 12 '15 at 13:10

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.

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

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