uniqueness of division algorithm in Euclidean domain

Theorem. 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
Canonical name	UniquenessOfDivisionAlgorithmInEuclideanDomain
Date of creation	2013-03-22 17:53:00
Last modified on	2013-03-22 17:53:00
Owner	pahio (2872)
Last modified by	pahio (2872)
Numerical id	7
Author	pahio (2872)
Entry type	Theorem
Classification	msc 13F07
Related topic	KrullValuation
Related topic	Quotient
Defines	incomplete quotient