uniqueness of division algorithm in Euclidean domain

Theorem.  Let a,b be non-zero elements of a Euclidean domainMathworldPlanetmath D with the Euclidean valuation ν.  The incomplete quotient q and the remainder r of the division algorithm


are unique if and only if

ν(a+b)max{ν(a),ν(b)}. (1)

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


and  rr,  qq,  then the properties of the Euclidean valuation (http://planetmath.org/EuclideanValuation) and the assumptionPlanetmathPlanetmath yield the of inequalities


which is impossible.  We must infer that  r-r=0  or  q-q=0.  But these two conditions are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath (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.


Then we obtain two repsesentations


where  ν(b)<ν(a+b)  and  ν(-a)=ν(a)<ν(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