9

Euclidean and
Factorization Domains

Introduction
In this chapter we talk
about divisibility in rings in a
to Euclidean
Domains, Principal Ideal Domainsgeneralized fom, introduce the reader
Domains.(UFDs). prime and ireducible elements, polynomial(PIDs) and Unique Factorization
over rationals,
Noetherian rings., irreducibility criteria
rings.

Definition: Let R be a commutative ring. a, b e R, a 0, then

(a divides b) if 3 c e R s.t., b =
ac. Also then
we say a |b
a is called a
factor of b.
If a, b e R thenelement d e R is called greatest common
an
factor) ofa and b if divisor (or highest common
(i) d|a, d|b
i) whenever c | a, c |b then c |d
and in that case we write d
g.c.d. (a, b). In fact sometimes only (a, b) is used to
=

g.c.d. of a and b. denote

Remark: One can prove that
) If a | b, b |e thena lc
(i) If a | b, a |c thena|b +c
(iii) If a |b then a | bx for all x e R
If R has unity then 1 |x for all x e R and if a is a unit then a for
(iv)
|x all x e R.
Example 1: Consider the ring R {0, 1, 2, . 7 modulo 8
=

then since 2 3 6, 216

282 4, 214
Again, if c|4, c|6 then c16 - 4 c | 2
Thus 8.c.d.(4, 6) = 2

Also as 6 6 1, 4 = 6 ® 6
we find 616 and 6|4
9. Euclidean and Factorization Domains 9 398
Conve

Now if c |6, c|4

nen as c
|6, we get g.c.d.(4, 6) =
6. Thus it is possibie to navc more than one g.c.d. for
Same pair of
elements. the

Aample 2: In the ring E of even integers we notice 4 and 6 do not have a g.c.d.
( t h e only possibility) is n o t a g.c.d. o f 4 , 6 as 2 6 in E. Indeed 6 = 2 . 3 b u t then

¬ E. Of course, 2 is the unique g.c.d. of 4 and 6 in Z, the ring of integers.

Denition: Let R be a commutative ring. A non zero element e R is called least common
muliple (l.c.m.) of two (non zero) elements a, b E R iT
) a|1, b |I
(i) if a |x, b |x then 1 |x
We denote I
by l.c.m. (a, b) [a, b] =

ust as proved above one can show that a pair of elements in a ring may not have an Lc.m.
and a pair could have more than one 1.c.m. See exercises.

enton: Let R be a commutative ring with unity. Then a, b e R are called associates if b
ua for some unit u in R.
We recall here that bya unit we mean an element which has multiplicative inverse. The above
definition will not be 'complete' unless we show that the relation 'is an associate of 1s an
equivalence relation. If we denote the relation by ~
then a~ a
as a 1. a and 1 is a unit
=

a~bb ua where u is a unit =

b =a
b ~a
Indeed u will be a unit if u is a unit.
Finally a b, b~cb= ua
C vb for units u, v
Since c vb =
v(ua) =
(vu)a
Showing C~a
as uu =
1, vw =
1 (vu) (vu) =
(vu) (u) =1|
we notice vu is a unit.

Example 3: 3i -4 is an associate of 4i + 3 in complex nos.

Problem 1: Let R be an integral domain with unity and a, b e R be non zero elements such
that a b and b | a, then a and b are associates and comversely.

Solution: a lb b =xa
b a a =yb for some x, yER
b xa = x(yb)

b(1 - xy) = 0

1-xy = 0 as b #0
y is a unit in R and a = yb, and thus a, b are associates.
397 398 A Course in Abstract Algebra

Comverselhy, if a, b are associates then a unit u, s.t., a = bu (and so aul = b).

b a and a | b.
Theorem 1: Let R be an integral domain with unity. Ifd, g.c.d.(a, b) in R then d, is also
associates.
agc.d.(a, b) iff d, and d, are

Proof: Onc may remark here that we prove this result only after assuming the existence of
g.c.d.
Let d, and d, be both ge.d.(a, b).
Then d, |a, d, |b
and
by definition, we get d,|d, and d, 1d
d and d, are associates. (using problem 1)
Conversely, let d, = g.c.d.(a, b) and d, be an associate of d

Then ud, d,
=
for some unitu
d,|d, and as d, l a, d, |b
we find d, a and d, |b
Let xa, x | b then x | d, as d, is g.c.d. (a, b)
Also as d du
dd
and thus x|d
d g.c.d.(a, b).
Remark: In example 1 on page 396, 2 and 6 are g.c.d. of 4 and 6. We observe there that 2
and 6 are associates, as 6 2®3 and 3 is a unit in Zg (33 =1).
Theorem 2: Let R be an integral domain with unity. If , = l.c.m.(a, b) in R then l, is also

an 1.c.m.(a, b) iff 1, and l, are associates.

Proof: Follows similarly as the above theorem.

Problem 2: Let R be an integral domain with unity If gc.d.(a, b) = dfor a b e R then

cd and g.c.d.(ca, cb)) are associates.

Solution: Let g.c.d.(ca, cb) = d'

Since d | a, a = dk

ac =dkc
=
cdk
cd | ca
Similarly cd| cb cd|d >d =cdt
Again d| ca ca =ds
c a =d's cdts
a = (di)s dt | a

Similarly dt b
 9. Enchidean and Factorization Domains 4 0 0 Suppose
= 0
d(l
-

p)
|d d =dip
L e t

d
= 1p > 1 is a unit

8.c.d.(ca, cb)
=

d' =cdi
i.e., cd and d' are associates.

Euclidean Domainss
Euclidean ring) if for all
domain (or a
Deinition: An integral domain R is callcd a Euclidean
aER, a #0there is defined a non -ve integer d(a) S.l,
f o r all a, b e R, a #0, b # 0, da) s d(ab)
(i) for all a, b e R, a* 0, b # 0, 3 and r in R s.t.,
a = tb + r

where either r =
0 or d(r) <
d(b).
0 #aE L, detine
Xample 4: Consider the integral domain < Z, t. ,
> of integers. For any
d(a) =
| a|, then d(a) is non -ve integer.
Again, let a, b e Z be any elements s.t., a 0, b #0
then d(a) = |a1
d(ab) = | ab | = | a ||b|
thus da)s dab) as | a | | a | | b |
Again let a, b e Z (a, b # 0)
Suppose b>0, then it is possible to write
a = tb + r where 0 Sr<b

1,re Z
Ifr# 0 then r <b |r|<|b|
d(r) < d{b)
Ifb < 0 then (- b) > 0, . 31, r e Z s.t,
a =(-b)r +r where 0r<-b
a =(-9b +r
and if r 0, r<-b | r | < | b |
d ) < d6)

Hence Z, +,.> is a Euclidean domain.

Remarks: (/) When we say, in the defínition, that 3a non -ve integer
d(a) for any
0 a, we mean, 3 a function d from R {0} to Z" U {0} where Z is set
of +ve integers.
-

This function d is called Euclidean valuation on R. Also the last condition in the definition is
called Euclidean algorithm.
0) We can show that the and r mentioned in the last Euclidean algorithm) condiüion in
the definition of Euclidean domain are uniquely determined iff
da + b) s Max. {da), db)}.

Let da + b) s Max. {dla), db)} and

400 A Course in Abstract Algebra

Suppose a =
tb + r =

,b +
ri
Let r - r # 0, then b(t - t) = - r #0, and so t- 1, #0
Now d(b) s d{b - 1))

dr -)
Max. {dr). d(-r)} (given condition)
=
Max. {dr), d-r)}
< d(b) which is not possible.
Thus r-r=0 b(t -t) =0
or
-1 =0 as b 0
I =and ri r=

Conversely, let t, r be uniquely determined and suppose

d(a + b)> Max. {d(a), d{b)} for some a, b (non zero) in R.
Now b =
0(a + b) + b =1.(a + b) -a
Also d(- a) = d(a) < d(a + b)

and d(b) < da + b)

Thus for b, le R, 31 0,
=
r
=b or , =
1, r -a s.t, b = t.l + r, b =
4l +
where r (as a + b * 0) t # , a contradiction to the uniqueness.
Hence d(a + b) S Max. (da), db). Note that a Euclidean domain contains unity (sec cor.
ahead).
Theorem 3: Let R be a Euclidean domain and let A be an ideal of R, then 3
a,eA s . , A = {ax | xe R).

Proof: If A = {0}, we can take a, = 0.

SupposeA {0}, then 3 at least one 0 # a e A.

Let a, e A be such that d(a) is minimal. [Existence is ensured by the well ordering principle
which states that every non empty subset of non -ve integers has least element.]
We claim A is generated by this a
Let a e A, a * 0 then by definition, 31, r e R, s.t.,
a
a+r where either r =0 or d(r) < d(a
Suppose r

Then a EA, t eR>ta, e A

a e A, ta, E A a - ta, E A
reA
But da) is the smallest d-value in A and d(r) < d(a), which leads to a contradiction. Hence
r= 0
a = ta4

Thus any a e A can be put in the form ta

Aclax |xe R}
9.
Euclidean and Factorization Domains

| X E R} CA as a, e A > xa, e A for all x E*

Hence A {ar | x e R}
which proves the
theorem.
Definition: Such an ideal Awhich contains multiples of an element a, includ
cluding a, R is of
C a
Principal ldeal of R, generated by a, We denote this by A
=u (Ce page s42 also)
other words, the
by a smallest ideal of Rwhich contains a, is called Principal ldeal generated
n view of this definition the previous theorem will read as
Theorem 4: Every ideal in a
Euclidean domain is a
principal aea.
Cor.: A Euclidean
domain possesses unity.
r0Or: LetR be
a Euclidean
some
domain then R is its own ideal and, therefore, R is generated by
element r of R.
Thus each element of R is
In
a
multiple of r,
particular r is a
multiple of r
i.e., k for some k e R
Now if a e R is any element then
C) as R =

a
xr for somex
hence ak (xr) k x(r.k) xr, Ea
=
= =

i.e., k is unity of R.

Definition: An integral domain R with

ideal of R is a principal ideal. unity is called a Principal Ideal Domain (PID) if every
In fact, if R happens to be a
commutative ring with unity with above condition, we call it
a principal ideal ring.
In view of the previous theorem and cor., we get
Theorem 5: A Euclidean domain is a PID.
In particular thus, the ring < Z, +,
>of integers is a
independently PID. This result follows
if we recall (see exercise 1, page 394) that every ideal in < Z, +, > is a principal ideal.
Remarks: (1) A field F is always a PID as it has only two ideals F and {0}. F is
by 1 and {0} by 0. generated
(i) One can show that there exist PIDs which are not Euclidean domains. In particular,
ZI-19] ={a+ -19 b|a, b e Z} where a, b are both odd or both even, is a PID but not
a Euclidean domain.
(ii) See page 431 for an example of an ideal which is not principal
Problem 3: Show that in a PID every non-zero prime ideal is maximal.
Solution: Let P = (p). p * 0, be a non zero prime ideal in a PID R.

Suppose PEQ= (4) cR

Then pEPEQ=(q)
402 A Course in Abstract Algebra

P=qr
qr e P
g E P or r e P
Ifge P then all multiples of q are in P» QcP
thus P
I fr e Pthen r = p t > r= qrt

r(l - q) = 0

1= qt (r*0)
But e 0. teR~ g e Qle Q Q =R
Note r = 0 would mean p = q . 0 p = 0 < P = (0).

Remark: In view of problem 28 page 390 we find a non zero ideal in a PID is prime iff it
is maximal.

Problem 4: Find all the prime ideals o f , (n> 1) and hence of Z

(n)
A
Solution: We know any ideal of RIN is of the type where A is an ideal ofR, containing
N. (See Cor. Page 365)
Let (n) = N and n = p p 2 . p , where p, are distinct primes.

Letbe any prime ideal of then A is an ideal of Z. We show it is a prime ideal of

Z. Since A is an ideal of Z, it is of the type A = (a). Suppose A is not a prime ideal of Z. Then

x, y eZ, s.t., xy ¬ A but x and y are not in A.

Now xy e A Nxy e AIN NxNy e AIN
Nx or NyE AIN as AIN is prime ideal
x or y is in A, a contradiction.
Hence A = (a) is a prime ideal and thus a is a prime (see exercise 1 page 323). Also

(n) s (). Since n e (n) s() we find a|n.

But primes dividing n are p1, P2 P
Thus a =p,for same i, lsiar

Hence if Al(n) is any prime ideal ofthen it is of the type for some i,
(n) (n)
sisr.
Z
Conversely, any ideal of the type , lsisrwill be a prime ideal of
(n) (n)
Z/n)Z
as (p)/()(p)

Since (P) is a prime ideal of Z, i s an integral domain.

(P)
 9. Euclidean and Factorization Domains
Y404
L e tx

ZIn)(n
Thus (p.)/ 1S an integral domain and hence a r e prime ideals of 2
a n dy

(n)
ISisr. (ny
where p, are all the primes dividing n.

We thus conclude that if PP2) (P

are precisely the
n =

p P Pthen ((n) (n)

Z
prime ideals of
(n)
We've seen earlier (see page 365) that

e: Z, s.t.,
(n)
e(m + (n)) = m, 0 m <n
is an isomorphism.

Now if P is a prime ideal of , then P) is a prime ideal of Z

(n)
Since are all the prime ideals of their the prime ideals of Z,
(n) images under are
(n)
i.e., (P,). (P). (P) are all the pime ideals of Z,
Remarks: () n particular, prime ideal of Z, where p is prime is (p) = (0) as p =0 in Z, Recal
P
a field has no non-trivial ideals and
Z, is an ideal when p is prime.
(i) Since a non zero ideal in Z is maximal iff it is prime, the above result can similarly be
proved for maximal ideals.
Problem 5: Show that Zi| = {a + ib |a, b e Z}, the ring of Gaussian inlegers is a Euchidean

domain.
Solution: We know that Z[i] is an integral domain.

For any 0 #xe Z{i|. where x =a+ ib, define

dr) = d(a +ib) = a +6

Then as x # 0, either a * 0 or b # 0

thus da + ib) =d +b2> 0

Let now x, y e Z[i], s.t., x # 0, y # 0 and let r

=
a +ib, y c + id.
=

Then dxy) d(a + ib) (¢ + id) d(ac

=
= -

bd) + i(ad+ bd))

= (ac - bd) + (ad + bc

(a +b) (c+ d)
...(1)
dr) dy)
Sincey # 0, d(y) 2 1 y+0 means c or ds non zeroj
Thus doy)2dx
We now prove the last condition in the definition of a
Euclidean domain.
 A Course in Ahstract Algebra

A04 +ve integer n (x =

n + i0))
where x is an ordinary
be two members
Let x, y E Z
and y =
a + ib

Euclid's division algorithm,

By
a
=
un +
r 0sn<n
b = vn + '2
0S n

Noweither S, or >

then-5
n - j <n- =

a un + r, un tn -n +r
Thus n(u + 1) - (n - r)

ng +
& where k, = -

(n -

r)

Thuswhether 1sor
we can express

a =ng + k where |k|s

b ng + k, where |k2lS;
Similarly
a+ib n(g+ ig) + &, ik) t
+
i.e.
or y
=
tn +r [t =q + iq', r=k, ik]
where either r= 0 (k, & k, could be zero)

de)-d+ik)- kf +ks+«n - dn)

Thus, under this particular case, the result is proved.
Let Z[I] be any two non zero members then X* is a tve integer, say, n.
now x, y ¬
above result proved, to yx and n and find that
We apply the
For and n, 31, r e Z[i), s.t.,

yx =
tn +r
where either r = 0 or d(r) < d(n)

Ifr = 0 then yr = tn = txx = y = * + 0

If dr) < d(n) then d(yf - tn) < d(xT)

9.
Euclidean and
Factorization Domains
4 0 6

Similar
d( y -

txï ) d(x) d(T)

<
lusing (1)
d(F) d(y tx) < dx) d(T) -

dy tx) < dx) |d(F) > 0] -

Put
y tx =

r, then d(r,) < dx)

-

So
y tx =

+r where dr) < d(E)

combining, we get
y x =
+
rwhere either r =
0 or d(r) <
d(x).
Hence the result is
proved.
Problem 6: Show that
Z.v2] {a+ 2b|a, b EZ}
=
is a Euclidean domain.
Solution: It is
easy to see that Z[/21 is an inte gral domain. Define a
d:Z/2]-403 >Z by mapping.

d(a +2b) =
|d 2b -

then |a -

26212 1 as a2 2b? =0 2 =

which is not possible.

Again d(a + v2 b) (c + v2 d)] =

d[(ad + 2bd) + v2 (ad + be)]

=
| (ac
2bd) 2 (ad + bc)* + -

|(a 2b) (c2 -24) -

=
| a 2b|| 2 242|
-

(1)
2a 2b d(a +v2b) -
=

i.e., da+ v2b)s d[(a+ v2b)

Let
(c+v2d)]
now a+v2b and c+v2d be two members of
then Z[V2] and suppose c
+V2d *0,
atv2b (a+2b) (¢-V2d) ac -bdv2(bc-ad)
C+v2d c-2d2 c2-2d2 2-2d2
= m+2n (say)

then m and n are rationals.

Now m =
[m] + 8 where [m] is the greatest integer not greater than m and e is fractional
part of m.

If Os0take p ={m

and if <e<1, take p = [m] +1

Thus 3 integer
an p, s.t, |m- Pis
406 A Course in Abstract Algehra

Similarly we can find an

integer q. s.t., | n -q|S,
Put m -

p =
a, n -

p =B. l1s 11s

then

a+ 2b
Also then= (P+a)+2 (q +B)
,c+V2d

a+2b
(p+2 g) +(a+ v2 )
c+2d
a t v 2 b -(¢+V2d) (p +V2g) +(c+ vV2d) [(m - p) + v2(n-9)

where, of course, (p +24) ¬Z{V2] as p, q are integers

we can thus write

at 2b (c+ v2d)(p + v2g) +r

where r=
(c+2d)[(m -p)+v2 (n -4)]
and as r= (a+2b) -(¢+v2d) (p+v2g)
we notice re Z[2]
Now if r*0, d ) = d[(c+2d){(m -P) + (n -g) v2}|

=
d[(¢ + 2d)|d(m p)+ v2(m-q)-

using (1) one may notice here that in proving (1) we do not essentially require that a, b, c,
d are integers
d r ) = | c - 2d|| (m - p - 2 (n - q*|

s|e- 2d |I|(m p)* -

+ 2 (n -q)|
sl-
s|e-2d1-d(¢+v2d))
Hence, for a+ v2h,ctv2de Z{V2] 3p+v2 q, re Z{V2] s
(a+2b) (e+v2d) (p+l2d)+r
where either r = 0 or d(r) < d(¢ + v2 d)

showing that Z[/2] is a Euclidean domain.

Theorem 6: Let a, b be two non zero elements ofa Euclidean domain R. Ifb is not a unit
in R then d(a) < d(ab).

Proof: Let b be not a unit. Then for a, ab in R 31, r eR s.t.,

a tab +r
 4408
9. Euclidean and Factorization Domains w h i ca
hr e a

Theore
where either r = 0 or d(r) < d(ab)
i sp o s

If
r=0, then a =tab a (l f b) 0 -
=

is not so.
tb l or that b is a unit, which
=

Thus r 0 and d(r) <

d(ab)
Now r
=a - tab =
a(l - tb)
Hence da) s da(1 d(ab).
-

tb)) d) = <
O a, b are non zero elements of a Euclidean domain R then d(a) = d{ad) iht b is a unit

If b is a unit then 3 c s.t., bc =

1
Now d(a) s d(ab) s d(ab)c) =
d(a)
d(a) =d(ab)
Converse follows from above theorem.
roblem7: Show that an element x in a Euclidean domain is a unit iy ana ony y
d ) = d(1)

Solution: Let d(x) =

d(1)
Suppose x is not a unit, then by above theorem
d(1) < d(1 .) Taking a = 1, b =x

1.e., d(1) < d)

a contradiction
x is a unit.
Conversely, let x be a unit in R, then 3y e R s.t.,
y1
Now dr) s dry) (by definition)
dx) s d(1)
Also d(1) s d{l .1)
d(1) S d¢)
Hence dx) = d(1).

Problem 8: Show by an example that it is possible to find two elements a, b in a Euclidean

domain such that d(a) = d{b) but a, b are not associates.

Solution: Consider D =
{a + ib | a, b e Z} =
Z[i], the ring of Gaussian integers
where d(a + ib) = a + b

then D is a Euclidean domain. (See problem 5)

Here d(2 +13) = 13 = d(2 - 3
but 2 + 3i and 2 - 3i, are not associates.

Notice that units of D are #l, ti and thus an associate of 2 +3i can be
(2+3i)1, (2+3-1), (2 +31)1, (2 +3-i)
i.e., 2 + 3i, - 2 - 31, 2i -3, 3 - 2i
 408
A Course in Abstract Algebra

which are all different from 2 3i.

Theorem 7: Any two non zero elements a,b in
is
a Euclidean domain R have ag.c.d. d and it
possible to write.

d a+ ub for some A, u e R
Proof: LetA =
{ra + sb |r, s e
R}
then A is an ideal of R as
0 0. a + 0. b e A A # 0
Let X, y eA

X =r,a t ,b, y= r,at s,b

Thusxy =( - r2)a + (, - s,)b e A

Again x E A, rE R, X =ra +
s,b
= r { r , a + s,b) = (r)a + (rs)b e A
showing that A is an ideal of R.
Since a Euclidean domain is a
PID, A will be generated by some element, say, d.
We claim d g.c.d.(a, b)
Now d e A d= ha +
ub for some A. u e R
Again since a = 1.a + 0. b e A

b 0.a+1.beA
(Note R being a Euclidean domain has unity)
So a e A, A =() a= ad for some a e R
beA, A = (d) b = Bd for some B e R

d l a and d |b
Again, if c |a and c |b
then c| ha, cld
c ha +ub
i.e. cld d- gcd.(a, b).
Remarks: (1) The theorem clearly then holds in a PID, and the next
result that we prove in
aPID holds in a Euclidean domain.
(ii) Similarly one can show that any finite number of non-zero
elements
a,a., a, in a Euclidean domain (PID) Rhave a g.c.d. which can be put in the form
+Aa,t +, a, 2, e R. A,a,
Theorem 8: Any wo non zero elements a, b in a PID R have least
a common multiple.
Proof: Let A =(a), B (6) be the ideals
=

generated by a and b.
Then A n B is an ideal of PID R. Suppose it is
generated by .
We show l=lc.m.(a, b)
Now AnBCA,A nBcB
le () le (a) »l =
au
for some u
9. Euclidean amd Factorization Domains
410

E(=le (b) l bv for some v =

Thus

alland b | 1
Again, suppose a | x and b
|X
* =
aa. x bB a. ß ¬ R =

* e (a), x e (b)
* E AnB =
()
x = kl >1| X
Hence= l.c.m.(a, b).
cntion: In an integral domain R with unity, a., b (non zero) are said to be co-prime or
relatively prime, if
is a unit in R. g.c.d.(a, b)
rODiem 9: Two elements a, b in an integral domain with unity are co-prime w
g.c.d.(a, b) = 1.
Ouon: Let a, b be
co-prime. By theorem 1 any associate of a g.c.d. 1s a g.C.a.
Since 1 is associate of any unit
I will be an associate of d
g.c.d.(a, b) =
=
a unit
1
Converse is obvious 1 is
=

g.c.d.(a, b)
as a unit.
Problem 10: Let R be a PID and
a, b be two non zero elements of R. Show that
a, b] (a, b) abu where u is a unit and
=

(a, b) g.c.d.(a, b), [a, b] I.c.m. (a, b). = =

Solution: Let g.c.d.(a, b) =

d
L.c.m.(a, b) = !
Since R is a PID existence of d and I is
ensured. We show dl | ab and ab
Since | dl
I l.c.m.(a, b), a | I and b |1
=

we get I = au, l= b v for some u, v ¬ R

Again d g.c.d(a, b) x, y e R, s.t.,

ax +
by =d (theorem done)
> I (ax + by) = dl

l a x + lby = dl

b v a x + auby = dl
ab(vx + uy) = dl ab | d

Again as d|a, d| b, a = da, b = dß, a, ß e R

..(1)
ab =
d a d ß= d(aßd)
Now a = d a and d a
daß
dß and dB | daß
b
a doß, b | daß
l | daßB
daß = Ik for some k
 410 A Course in Ahstract Algebra
Thus ab =

d(oßk) =
(dl)k
dl | ab
() and (2) imply dl = uab 2)
where u is a unit (result
proved).
Note: Sec page 433 for method
explaining how to find g.c.d. in general.
Prime and Irreducible
Elements
Definitions: Let R be a commutative
if ring with unity. An clement p e Ris called a prime element
0) p* 0, p is not a unit.
(i) For any a, b e R, if p | ab then
p | a or p |b.
Let R be a commutative
ring with unity. An clemcnt p e R is called irreducible
an
elemen
() p* 0, p is not a unit.
(ii) whenever p ab then one of a
=

or b must be unit. (In other

a
words, p has no proper
factors.)
Example 5: In the ring <
Z, +, >of integers, every prime number is a prime clement as well
as irreducible clement.

Example 6: Cosider the ring

ZV-5] ={a +-5b |a, be Z}

under the operations defincd by

(a+-5b)+ c+V-5d) =
(a + c) +
-5(b +d)
(a+y-56). (c+-Sd) =
(ac -

5bd)+ N-5(ad +bc)

()We show -5 is a prime element.
-5 #0, it is also not a unit as, if it were a unit then 3 a+v-5b, s.t.
-Sa+-5b) =1
V-5 = 1 + 5b, which is not possible as R.H.S. is an integer whereas L.H.S. is not an
integer.
Suppose now v-5 divides (a +-5b(c +-Sd),
then 3 (r+-5y) s.t.
-S(x+-5y) = (a+v-5b) (c + V-Sd)

which on comparison gives,

-5y = ac - Sbd

S(hd y) = ac 5 | ac

But 5 being a prime number

either 5|aor 5|c.
9. Euclidean and Factorization Domains
411

If 5 | a then W-5x-5)1 a
-5|a
-5|a+ b-5
Similarly, if 5 |c then -5|c+-5d
Hence -5 is a prime clement.
(i) We show further that 3 is an irreducible element which is not prime.
Suppose 3 (a+-5b) (c +-5d), a, b, c, de Z
Taking conjugates, we get
3 =
(a--5bNc -V-5d)
Thus 3.3 +5bXe +s)
i.e. 9 (a+5b*(c* + 5db)
a + 5b = 1, 3 or 9
Now a + 56 = 3 is not possible as a, b e Z

Ifa +5b = 1 then a = + l and b = 0

If a+5b = 9 then a* + 5d = 1, giving c =+ I and d = 0

Thus, if o+ 56= 1 then a+-5b = +l = unit (see Problem 11 below)

and if a+ 5b = 9 then c+y-5d = +l = unit

Hence 3 is an ireducible clement of ZV-5

Now (2+-5)(2-V-5) =9 and thus

312+-5%2-V-5)
We show it does not divide any one of these. Suppose 3|(2 +-5) in Z.V-5]
Then (2+-5) 3 (a+v-56) a, be Z
2 - - 5 = 3(a -v-5b)
9 9 (a + 56)
l =a + 5b a =+ 1, b = 0

2 + -5 =+3 which is not possible

Thus 3 (2+V-5). Similarly 3 (2-V-5)
Hence 3 is not a prime element of z{v-5].

Problem 11: Find all the units of zV-5.

Solution: Suppose a +v-56 is a unit in Z.V-5].
Then (a+56Xc +-Sd) - I+/-5.0 for some c, d e Z
 9E
.u c l i d e a nand

A Course
412 Abstract Algebra
in Abstract
Cor..i

I I
So. (a-v-5bMc - V-5d) = =

true

gving ( a 5 6 c +5b) = I in Z
a+5b= 1 a =+1, b = 0
Thus a+V-Sb =
+1 are the units in ZV-5]
The following theorem exhibits the 'closeness' of prime and irreducible clements.
heorem 9: In a PID am element is prime if and only if it is irreducible.
0Let be a PID and letp e D be a prime element. We need prove only that if p = ab,
then a or b is a unit.
So let p =
ab thenp | ab
p l a or p |b (p is prime)
If pla then a =px for
So some x
P= ab =(px)b
P(1 xb) =0
1 - xb = 0 as p * 0

b xb =
1
Similarly. if p |b then a will be ais unit.
a unit.
Converse ly, let p be irreducible clement
plaor p |b. and suppose p | ab. We show Cither
Ifp la, we have nothing to
prove.
Suppose Pa
Since p, a are elements of a PID
We show d is they have a
g.c.d., say, d.
a unit.
Nowd p and d | a
3 u , s.t., p du,v =
a =
dv
f d is not a unit then as p is irreducible and p =
du, u will be a unit
uexists
pu = d

Thus d is a unit.
a
pu'v>p|a which is not so.
Again, we know that d can be expressed as
d na + P
which gives
dd d 'ha + d'wp=

But
b.1= Ad ab + ud'bp
P| ab, p ud' bp
| (abrdl p +
ud bp)
p|b
Hence the result follows.
 413
Factorization Domains
9. Euclidean and

irreducible. The converse is not

domain with unity, every prime clement is

Cor: In an integral
true. See exercises.

above theorem, we can say ZV-5|

of Example 6 and the
Remark: Combining the results
is not a PID.
mod 6.
the ring 2, {0, 1, 2, 3, 4, 5}
=

Example 7: Consider
in Z, but is not irreducible.
2 is a prime clement
non unit.
2 is, of course, non zero,

2 a ®b
Suppose
ab = a b for some
Since
we find 2 | ab
and as 2 | 6g, 2 | a ® b,
2 a or 2|b
2|a or 2 |b in Z
element.
Hence 2 is a prime irreducible. (Note,
find 2 is not
Again, as 2, where
2 4 = neither 2 nor 4 is a unit, we

domain.)
Z, is not an integral (a) is a maximal ideal
field, then an ideal A
=

a PID which is
not a
Theorem 10: Let R be
irreducible element.
and only if a, is
if
an

be maximal ideal.
Proof: Let A
=
(a) a

( a, 0 . does not exist.

Suppose a,=0, then since R not a
is field, 3 at least one 0 #be R, s.t,6
Let B =
(6)and as
a, 0, A (0) = =

and
()cBcR >A cBsR
B#A as b e B, b * 0, and A = (0)
Now
B+R as 1 e R, but 1 e B

then 3 some x s.t, I

=
bx
Note if 1 e B =
(6)
invertible which is not so
Showing that b is
Hence 0.

not a unit.
i) a, is
1
unit, then a,a
=

Suppose a, is a
A
a, A, aeR~ a,a e

leA

A =R
which is not possible as A is maximal.
Thus a, is not a unit.
R. We show either b or c is a unit.
(ii) Let now a,
=
bc for some b, c e

Let B (6)
Since ¬ B
abc, a,
a l l multiples of a, are in B

AcB
 A Course in Abstract Algebra

414

R B =
A
But A is maximal thus either B = or

R
IfB =
R. then 1 e B (b) as
Ie
l = xbfor some x

b is a unit.
IfB A, then b e A = (a)
b =ya, for some y

a=be =ya,
a-yac = 0

a,(-yc) = 0

1-ye =0 (as a, * 0)
c i s a unit.
Hence the result is proved.
Conversely, let a, be irreducible element.
We show A
(a) is maximal.
=

Let I be any ideal s.t, A

clcR.
Since R is a PID, I is
generated by some element, say, *
Now x e A as if x e A
then
)CA
1.e., IcA but Asl
means A = I which is not s0.

Thus A.
Again, A = a)cI

a, y for some y
a. is irreducible >x or y is a unit.
Ify is a unit, then yyl =1
and

But
a, e A, yeR> ayl eA
x e A, which is not true.
Thus y is not a uniIt.
So x is a unit and xxl =1.
Now xeI, x' eR, I is an ideal
xxeI>1eI>l=R
Ais maximal ideal of R.
Remark: Recall, a field F has
irreducible.
only two ideals F and {0}. F is not maximal and 0 is not
9mean mnd Tn torizatm Dmal 415

xerchen
. In a Euclidcan domain W with valuation d, sheow that
() d) - dl ) for all o 4 a e W

(i) if a, b are associates then da) - d(h)

(i) if a |h and da) db) then a, h are asciates

(iv) i ffor 0 4 a e R , d a ) - (0 then a i s a unit

(v) if a | b and a is nol an associate of h then day db), (1, h 4 0)

2. In a commutative ring k with unity. Prove that associate of a prime (irreducible)
clement is prime (irreducible)
3. If p, q arc primc clements in an integral domain with unity such that p | 4 then show
that p, q arc associatcs

4. Show that
() in L.c.m. (3, 6) 6 and 2
Z
=

(i) in 8c.d. (9, 18)

-

9, Lc.m. (9, 18) 1%

(20)
(ii) in ring of even integcrs, Ie.m. (4, 6) does not exist

(v) i n 2 6 , 8 have no Lc.m

(12)
5. Let R be a PID. Show that
yE R s.t., hy 1
() two non zero clements a, b arc co-prime iff 3x, ax +
=

(i) if a | he and a, b arc co-prime thenalc

6. Show that every ficld is a Euclidean domain

7. Prove that in 2 is a prime clement but not irreducible.

(8)
8. If A, B, C are ideals in a PID R, prove that
()An(B + C) =A nB+A n C
(i) A +(Bn C) = (A H)nA C)
9. Show that quoticnt ring of a PID is a PID and the same is truc of the homomorphic
image.
10. Show that +1, +i are the units in Z]4| and prove thatifa + th is not a unit in Z{i| then
+b> 1.
1. Prove that 1+ i is an irreducible clement in the ring Z4/| of Gaussian integers.
12. In the ring Z-5 - {a+-56|a,be 7}, show that 1+3-5 is imeducible element
but is not prime.
13. Show that in Z-3. 1+-3 is ireducible but not prime clement.
14. Show that in an integral domain R with unity, any pair of non zero clements has g.cd.
iff it has l.c.m.
416 A Course in Abstract Algebra

15. Show that ZJV3] = {a+ V3 b|a, be Z} is a Euclidean domain.

16. Let A = (a). B = (b) be two ideals in an integral domain with unity. Show that

4 B iff a and b are associates. Show further that if ( a ) + (b) = (d). then
d =

g.c.d. (a, b).

T7. LetR be an
integral domain with unity. Show that an element 0 #p E R Is a prime
clement iff (p) is a prime ideal.

Polynomial rings
Let R be a ring. By
polynomial over R, we mean an expression of the form
a

S) a, +a,x + a +a,"
=
a, e R .

What is x? The symbols x, x, here are not unknown elements or variables from the ring
. .

R. These are there

only for convenience, say as place indicators for the elements a, a2
of the ring. The idea behind the
notation is only our familiarity to polynomials of this type that
we are so used to
(and there, of course, x does represent a variable). A further justification of
this notation follows when we come to
defining addition and multiplication of polynomials in
the usual way.
Altermatively, any infinite sequence (a a, a, ..) of elements of R is called a polynomial
over R if all except finite number of its terms
a, are zero. (Thus after a finite number of terms,
all members will be zero). The first term a, is called the constant term of the polynomial. If
m is the
largest non negative integer such that 0 , then is called the lasta a (or leading)
cocfficient of the polynomial.
If S ) = a , + a,x + . +a" a, E R*

& ) = b ,+ b,x + . + b " , b, e R

be two polynomials over R, then we say J (x) =
gr) ifm and a, for all i.
b,
=
n =

Again, addition of polynomials f (r) and gr) is defined by

f ) + 8 ) = (a, + b) + (a, + b,) x + (a, + b,) .
Product is also defined in the usual way,
S() g(r) = (a, + a,* + . +a,") 6. + b,r +
+bx)
ab+(a,6.+ ab) x
Y" n

C+CX+ C **+ Cm+n n

where C a b + a,b-1 * . +a
Let now R[x] be the set of all polynomials over R. Then R[x] is a non empty set and addition
and multiplication as defined above on the members of R[r), clearly are binary compositions.
It is easy to see that R[x] forms a ring under these operations. Zero of the ring will be the zero
polynomial
Ox) = 0 +Ox +Ox
Additive inverse o f f (x) = a, t a,x + t a " will be the polynomial
I then the
-S() =

a a,r +.. +(-a)".

m
In fact, if R has unity polynomial
ex) = 1 + Ox +0x?
9. Euclidean and Factorization Domains 417

will be unity of R[{x]. e(x) is also sometimes denoted by 1. Instead of a ring R if we start
with a ficld F we get the corresponding ring Fx] of
polynomials.
Remark: Let R = Z, = {0, 1, 2} modulo 3. Define

f: ZZ S., S) =x*' +2x and

8: Z,s.., g) =r+2x
Then S0) =0 s(). s(1) =1 +2 =g(1)
S(2) 5 +l =2 +4 = g(2)
Hence f(a) = gla) V a e Z

and thus S ) = 8 ) by our definition of a function.

On the other hand we notice

S(x)= (0, 2, 0, 1, 0, 0,...)
g) = (0, 2, 0, 0, 0, 1, 0, ..)

are not equal as polynomials over

Z. Thus f () + g() in Z,¥].
Definition: Letf) = a, + a,r + a + . : + a " be any non zero polynomial inR[x]. We
say S ( ) has degree m if a, # 0 and a, = 0 for all i> m, and write
deg f(r) = m.

We do not define degree of zero polynomial.

We say degree off) is zero if a, + 0, a, = 0 for all i> 0. In that case it is called a constant
polynomial. Also clearly, deg ( - f ) ) = deg f ) .

Suppose R is any ring and R[:] is the corresponding ring of polynomials over R. If we define
a map
S:R>R], s.t,
S) =a + 0.x +Ox +
then it is easy to see that f will be 1 - 1 homomorphism. Indeed,

Sa + b) = (a + b) + Ox + Ox +.

= (a +0x + Ox + +(b +Ox + Ox2+)

flo)+f6)
S(ab)= ab +0.x + 0.x+
=
(a + Ox +Ox + ) 6 +
Ox + )
f(a) sb)
Hence R can be imbedded into the ringR]. In other words, R is isomophic to a subring
of R[x]
Thus R can be identified with a subring of R[E] in view of which we sometimes take the
liberty of calling R to be a subring of R[r]. The following theorem is now easy to prove.
Theorem 11: Let R[x] be the ring of polynomials over a ring R then
() Ris commulative if R[¢] is commutative.
(i) R has unity iff R[x] has unity
 A Course in Abstract Algehra
418

roof: () IfR[r] is commutative then any subring of R{x] is commutalive and as R is Isomprphic

to a subring of R\x], R will be commutative.

Conversely, if R is commutative
and S(x) = a, t a,r t a r t ta"
Rt) = b, + bx t bx t +h
be two membcrs of
R|x], then by definition of product
S()g(r) a,b, + (a,b, t+ a,b,x+
=

b,a, +(b,a, +b,a*

8)Sr).
(i) If R has unity then the polynomial
e(x) = 1 + Ox + 0x2 +
is unity of R[x] as s(x)e(r) will be f(x) for any
polynomial fx).
Conversely, let R[x] have unity.
Definc a map 6: R[x] -R, s.t.,
6(S(x)) =

6a, t a,xt.. t a,") =

a,
then 6 is an onto
Thus R is a
homomorphism.
(Sce theorem 15).
a
homomorphic image of R[x] and hence has
unity, as homomorphic image of
ring with unity is a ring with
of R[x] unity. It fact, 6 (e(x)) will be unity of R where e(x) is
unity
Theorem 12: Let R[x] be the
ring of polynomial of a ring R and
suppose
S(x)= a, + a,x + +
a"
gx) = b, b,x+ + +
bx"
are two non zero
polynomials of degree m and n respectively, then
() Iff)+ g) * 0,
deg(f(x) + gx) S max(m, n)
(i) IfSo) gT) * 0, deg (S(x)
g(x)) Sm + n
(iii) IfR is an integral domain,
deg (S(x) g(x)) m- =

(iv) R is an integral domain

if R{x] is an integral domain.
(v) IfF is a field,
Flx]) is not a field.
Proof: () By definition,
S)+ g) =(a, + b) *+ (a, +
where
b,)x + (a, + b,)x*t:* + * (a, + bx
I max (m, n).
Now
a+ b= 0 for all k> I as a, 0,
b,
=
=
0
thus degree of f (x) + g(x) is less than or cqual to I =

have deg G ) +
g(x) < max (m, n). Consider the
max (m, n). Notice it is
ring Z of possible to
Let S ) = 1 + 2x 2x integers.
8 ) = 2 + 3x + 2x2

be two members of
Z[x].
then Sx) + g(x) = (1 + 2) + (2x -
3x) +(-2x +
2x)
=3 Sx
9. Euclidean and Factorization Domains
419

I whereas deg f(*) =2 =

deg g()
() 8*)) =
+
Thus deg
(ii) Let ) g*) = ©%ot C + c t *

where

Here mtn"m + n
t
a,m+n -1t*
t
a . .

ta+o

would be zero. (a+,= 0, b,,,

=
0 for all i, j > 0).
as all other terms
= 0 for allt> 0 and
Again, m +n+
be zero even if a, * 0 b, # 0)
thus ( ) gt)) Sm+n (ab, can
deg
We show that it is possible that deg S) g))
<m+n

Consider the ring R {0, 1, 2, 3, 4, 5} modulo6

=

Take Sx) =
1 + 23
8r) = 2 +x+ 3x
two polynomials in R[F] of degree 3 and 2 respectively.

Here
S)er) = 2 +x + 3x2 + 4+ 2x
which is of degree 4 <5.

integral domain.
Notice, here R is not an
0, therefore, ab, # 0 and hence
(i) If R is an integral domain then as a 0, b, *
+ .
, , * 0 showing that deg (S()8())
=
m
Cm+ subring of R[r],. R will
then since R is isomorphic to a
iv) If R[x] is an integral domain
also be an integral domain.

Conversely, suppose R is an integral domain.

of R[x] s.t,
Let f), g(r) be any two non zero members
So)g) =0
J ( ) = a, t a,x + * + a
where
g(x) = b, + b,r + +b"

be constant polynomials as then a# 0, b, # 0

Now both f(x) and g(x) cannot

(so C ab.* 0)
SMg(x) # 0
Since at least one off«), g{r) is non constant polynomial, its degree is 2 1.
R being an integral domain

deg f)gr))
=

deg s() + deg g(r) 21

which is a contradiction as it implies then C# 0 for some k> 0
S)gt) = 0.
whereas
0 ft) 0 gr) =
0
SMg(x) or
=

Hence =

R F ] is an integral domain.
(v) Let F be a field, then since F is commutative, has unity, by previous results we find FJr]
will be a commutative ring with unity. In fact F being an integral domain, F[x] will also be an

integraldomain. We show, not all non zero elements of F[x] have multiplicative inverse. Consider
the non zero polynomial
 420 A Course in
Abstract Algebra
Sa) = 0 + lx + Ox +0x* +... (= a , t a,x t a *..)

Suppose gr) = b , + b , r +b,* is its multiplicative inverse

then
SOgr) C, t C*+ cx* =

should be unity e(x) =1 + 0x +

0r +. of F\¥]
C1c 0 for all i> 0
where
a b = 0.b, =0 # 1
Hence no g«) can be multiplicative inverse of
Sx) =
X.
Showing that FJx] is not a ficld.
R 1s a
ring, we get
R[x] the corresponding ring of
can similarly get R[x, y] the
Since R[¥] is polynomials. a ring, we
the
process can corresponding
be extended. Elements ring of polynomials of R[E] and
of R[x, y] will be of the
type
8 ) +Sy +S4*y +
+,)y"
where S) e R{). i =1, 2, n
fFis a field then
We shall use it a F\r] is a
ring with unity and
little later when we come to
similarly F[x, y] will be a ring with unity.
Problem 12: LetR andSbe
factorisation domains.
wo
isomorphic rings. Show that R[x] and S{x] are also
Solution: Let : R isomorphic.
Define a mapping
S be the given isomorphism.
S: RIx]- S¥], s.t.,
Sa,t a,xt. +a,) ¢(a,) =

It should now be a routine + o(a,)x + +

o(a,)r.
exercise for the reader to show that this S is
Problem 13: (i) Show that the an
isomorphism.
mapping
0: Q] > Qk], s.t,
of) =f(ax +
b), a, be Q. a 0 is
(i) Prove that any
automorphism of
an
automorphism.
Qx] is of the form as in ()
Solution: (i) We show o as defined above is ring automorphism
a
Since o r) +
8) =
o (hlr) where h(r) x) + =

gtr)
h(ax + b)
lax +b) +g(ax + b)
a r)) + a
=

and (ht))
o r)gr) =
a(rc), where r(t) SNgtr) =

=
r(ax + b) Aax + b)g(x + =

b)
o is a homomorphism.
Let
Sx) e Ker o be any member, then
ox)) 0 =

i.e.. Aax + b) =
0
Suppose J) = aotar+ ta,x"
*