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

a=qb+rwherer=0orν(r)<ν(b)

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

{a=qb+rwithr=0ν(r)<ν(b),a=qb+rwithr=0ν(r)<ν(b)

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

ν(b)ν((q-q)b)=ν(r-r)max{ν(r),ν(-r)}<ν(b)

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.

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

Then we obtain two repsesentations

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

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