# uniqueness of division algorithm in Euclidean domain

Let $a,\,b$ be non-zero elements of a Euclidean domain $D$ with the Euclidean valuation $\nu$.  The incomplete quotient $q$ and the remainder $r$ of the division algorithm

 $a=qb+r\quad\mbox{where}\quad r=0\;\;\mbox{or}\;\;\nu(r)<\nu(b)$

are unique if and only if

 $\displaystyle\nu(a+b)\leqq\max\{\nu(a),\,\nu(b)\}.$ (1)

Proof.  Assume first (1) for the elements $a,\,b$ of $D$.  If we had

 $\displaystyle\begin{cases}a=qb+r\quad\mbox{with}\quad r=0\;\;\;\;\lor\;\;\nu(r% )<\nu(b),\\ a=q^{\prime}b+r^{\prime}\quad\mbox{with}\quad r^{\prime}=0\;\;\lor\;\;\nu(r^{% \prime})<\nu(b)\end{cases}$

and  $r^{\prime}\neq r$,  $q^{\prime}\neq q$,  then the properties of the Euclidean valuation (http://planetmath.org/EuclideanValuation) and the assumption yield the of inequalities

 $\nu(b)\leqq\nu((q^{\prime}-q)b)=\nu(r^{\prime}-r)\leqq\max\{\nu(r^{\prime}),\,% \nu(-r)\}<\nu(b)$

which is impossible.  We must infer that  $r^{\prime}-r=0$  or  $q^{\prime}-q=0$.  But these two conditions are equivalent (http://planetmath.org/Equivalent3).  Thus the division algorithm is unique.

Conversely, assume that (1) is not true for non-zero elements $a,\,b$ of $D$, i.e.

 $\nu(a+b)>\max\{\nu(a),\,\nu(b)\}.$

Then we obtain two repsesentations

 $b=0(a+b)+b=1(a+b)-a$

where  $\nu(b)<\nu(a+b)$  and  $\nu(-a)=\nu(a)<\nu(a+b)$.  Thus the incomplete quotient and the remainder are not unique.

Title uniqueness of division algorithm in Euclidean domain UniquenessOfDivisionAlgorithmInEuclideanDomain 2013-03-22 17:53:00 2013-03-22 17:53:00 pahio (2872) pahio (2872) 7 pahio (2872) Theorem msc 13F07 KrullValuation Quotient incomplete quotient