Number Theory: An Introduction to Mathematics

104 II Divisibility

4 EuclideanDomains..........................................

An integral domainRis said to beEuclideanif it possesses a Euclidean algorithm, i.e.
if there exists a mapδ:R→N∪{ 0 }such that, for anya,b∈Rwitha=0, there
existq,r∈Rwith the properties

b=qa+r,δ(r)<δ(a).

It follows thatδ(a)>δ( 0 )for anya=0. For there existq 1 ,a 1 ∈Rsuch that

0 =q 1 a+a 1 ,δ(a 1 )<δ(a),

and ifan=0thereexistqn+ 1 ,an+ 1 ∈Rsuch that

0 =qn+ 1 an+an+ 1 ,δ(an+ 1 )<δ(an).

Repeatedly applying this process, we must arrive ataN =0forsomeN, since the
sequence{δ(an)}cannot decrease forever, and we then haveδ( 0 )=δ(aN)<···<
δ(a 1 )<δ(a).
By replacingδbyδ−δ( 0 )we may, and will, assume thatδ( 0 )=0,δ(a)>0if
a=0.
Since the proof of Lemma 9 remains valid ifZis replaced byRand|a|byδ(a),
any Euclidean domain is a principal ideal domain.
Thepolynomial ring K[t] is a Euclidean domain withδ(a) =|a|= 2 ∂(a).
Polynomial rings are characterized among all Euclidean domains by the following
result:

Proposition 21For a Euclidean domain R, the following conditions are equivalent:

(i)for any a,b∈R with a= 0 , there exist unique q,r∈R such that b=qa+r,
δ(r)<δ(a);
(ii)for any a,b,c∈R with c= 0 ,

δ(a+b)≤max{δ(a),δ(b)},δ(a)≤δ(ac).

Moreover, if one or other of these two conditions holds, then either R is a field and
δ(a)=δ( 1 )for every a= 0 ,or R=K[t]for some field K andδis an increasing
function of||.

Proof Suppose first that (i) holds. Ifa=0,c=0, then from 0= 0 a− 0 =ca−ac,
we obtainδ(ac)≥δ(a), and this holds also ifa=0. If we takec=−1 and replacea
by−a,wegetδ(−a)=δ(a).Sinceb= 0 (a+b)+b= 1 (a+b)+(−a), it follows
that eitherδ(b)≥δ(a+b)orδ(a)≥δ(a+b). Thus(i)⇒(ii).
Suppose next that (ii) holds. Assume that, for somea,b∈ Rwitha=0, there
exist pairsq,randq′,r′such that

b=qa+r=q′a+r′, max{δ(r),δ(r′)}<δ(a).

From (ii) we obtain firstδ(−r)=δ(r)and thenδ(r′−r)≤max{δ(r),δ(r′)}<δ(a).
Sincer′−r=a(q−q′), this impliesq−q′=0 and hencer′−r=0. Thus(ii)⇒(i).