Groups, Rings and Fields (Springer Undergraduate Mathematics Series)

fa,b : x -+ a + bx (x E IR) . Then,

as

in an Exercises 4. 1 , no. 2 O

fc,d fa,b = fc + ad, bd (a, b , c, d E IR) . Let T be the set of such mappings fa,b for which b "I 0. We claim that T is a group. Certainly we have closure since if b "I 0, d "I 0 then bd ::p 0 and so 0

fc,d fa,b = fc + ad, bd E T.

I ntroduction to Groups

109

The circle composition of mappings is associative and /0 , 1 is such that fo,l

0

fa,b = fa,b ·

For given a, b E lit, b # 0 we require to find c, d E lit, d # 0 such that fc,d 0 fa,b = fo,l ·

But this is only possible if bd = 1 .

c + ad = 0,

However we do have a unique solution, namely

We therefore conclude that T is a group as claimed. 3. Let

X =

lit \ {0, 1 } . Six mappings, e, a, b , c, d, J, are defined on e(x) = x,

X-1 a(x) = -- , x X d(x) = , x-1

b (x) =

-

1 -1 -x

X

as follows.

c(x) = 1 - x ,

1 f (x) = - . x

It is easy to verify that these mappings are defined on X and fairly easy to verify that they map X into X. We claim that these six mappings under the circle composition of mappings form a group of order 6. Closure is not obvious and must be verified somewhat tediously since there are 36 possible products. Associativity, on the other hand, is clear since the circle composi­ tion of mappings is associative. e must play the role of identity. The easiest way to verify closure etc. is to construct a Cayley table. By way of illustration we shall evaluate three products, leaving the reader to contemplate and per­ haps to evaluate some at least of the remaining 33.

() (:)

1 -1 1 1 x = = (a o !) (x) = a( f (x) ) = a -; .!_ X ( ! o a) (x) = f (a(x)) = 1

x

1

( )

=

x

� x = 1 - x = c(x) ,

: 1 = d(x) ,

x-1 1 x ( b o d ) (x) = b(d(x) ) = b -- = = =1-x x x-1 1 - -- x - 1 - x x-1 = c(x) .

Groups, Rings and Fields

110

Then a o f = c, f o a = d, b o d = c. Eventually we obtain the Cayley table. e

a

b

c

d

f

e

e

b

a b

c d

d

a b

a b e

f

c d

c d

f c

a d

f c

f c

e

b

f

d

a b

e

f

f c

a b

a

e

e

d

We shall later have occasion to refer to this table. In any subsequent discussion we shall omit o and write simply, for example, af = c, fa = d, bd = c, etc. 4. Let X = { (x, f) l x, t E R} . For each v E R we define a mapping Ttl where Ttl : X -+ X by

Ttl(x, t) = (x - vt, t) .

We claim that the set S of such mappings is a group. For u, v E

Thus

R we have

(Tu o Ttl) (x, t) = Tu(Ttl(x, t) ) = Tu(x - vt , t) = (x - vt - ut, t) = (x - (u + v) t, t) = Tu + tl(x, t) .

from which we obtain closure. The associativity of mappings is assured and T0 is evidently the identity. Further

T_tl o Ttl = T_tl + tl = To . and so

T_tl = (Ttl) -1 • S is a group and is Abelian since 0

0

Tu Ttl = Tu + tl = Tti + U = Ttl Tu . We remark that this example has its origins in the physical world. If we regard (x, t) as the coordinates of space and time and v as the speed then S is the group of Galilean transformations of classical mechanics (after G. Galilei, 1564-1642) . (See also Exercises 4.2, no. 10.)

I ntroduction to Groups

111

Defi nition 7 The group G is said to be cyclic if every element of G is a power of some given element of G. This given element is said to generate, or to be a generator of, the group G. ThUB if G is cyclic we may write G

=

{ an

: n =

0, 1 , . . . }

for some a E G. A cyclic group is necess arily Abelian.

Exa m ple 1 2 The groups of orders 1 , 2 , 3, 4 , with Cayley tables as given above, are all cyclic with the exception of the Klein four-group. In the case of the group of order 3 we 2 may put b = a and in the case of the cyclic group of order 4 we may put b = a3 , c =

2 a •

We now come to a UBage of the word 'order' which differs from its previoUB UBage but which, as we shall later see , is related to that previoUB UBage.

Defi nition 8 Let a E G. Then a is said to have finite order if for some n E N, an = e . If n = 1 then a = e and e is said to have order 1 . If for 0 < m < n, am =F e then a is said to have order n . If a does not have finite order then a is said to have infinite order. In a finite group all elements have finite order but if all elements of a group have finite order it does not necessarily follow that the group is finite.

Exa m ples 13 1. The additive group Z has one element, namely 0, of order 1 and all other ele­ ments are of infinite order. 2. The multiplicative group Q \ {0} has one element of order 1 , namely 1 , and one element of order 2, namely - 1. All other elements have infinite order. The assertions are true of the group IR \ { 0} . 3. The multiplicative group C \ { 0} has no real elements of finite order other than ±1 but there are complex elements of finite order. We may identify these elements by UBe of De Moivre's Theorem (after A. De Moivre, 1667-1754) .

Groups, Rings and Fields

112

Let z E C \ {0} and let z = r(cos O + i sin O) (r, O E IR, r > O) . Then we have, for n E N, i' = rn (cos 0 + i sin Ot = rn (cos nO + i sin nO) .

Hence zn = 1 if and only if rn cos nO = 1 , rn sin nO = 0. This holds if and only if

rn = 1, cos n0 = 1, sin nO = 0, or r = 1 and nO = Thus i' = 1 if and only if

2k:rr (k E Z) .

2k:rr . . 2k:rr

z = cos - + 1 sm - . n n 4. Let G be the group of order 6 with Cayley table as in Examples 1 1 no. 3. Then a2 = b, a3 = ab = e, b2 = a, b3 = ab = e, c2 = d 2 = f2 = e. Thus e has order 1 , a and b have order 3, and c, d and f have order

2.

Defi nition 9 Let a, b E G. Then a is said to be conjugate to b if there exists x E G such that x - 1 ax = b. We have therefore defined a relation of conjugacy on a group G and we should therefore not be surprised to obtain the next theorem.

Theorem 7 The relation of conjugacy on a group G is an equivalence relation.

Proof We have to prove reflexivity, symmetry and transitivity for the given relation. 1. Let a E G. Then e - 1 ae = a and so a is conjugate to a for all a E G.

2.

Let a, b E G and suppose a is conjugate to b. Then there exists x E G such that x - 1 ax = b. Let y = x - 1 , then y- 1 = (x - 1 ) - 1 = x. We have y- 1 x- 1 axy = y- 1 by

Introduction to Groups

113

and so But xy = e and hence a = e - 1 ae = y - l by .

Consequently b is conjugate to a. 3. Let a, b, c E G and suppose a is conjugate to b and b is conjugate to c. Then there exist x, y E G such that x - 1 ax = b, y- 1 Jty = c. Let z = xy. Then z- 1 a z = (xy) - 1 a(xy) = y- 1 x - 1 axy = y- 1 by = c. Hence a is conjugate to c. This completes the proof of conjugacy.

D

Defi nition 10 Under the relation of conjugacy in a group G the equivalence classes are called the conjugacy classes. A typical conjugacy class is {x - 1 ax : x E G } which is the conjugacy class con­ taining a. In an Abelian group G each conjugacy class consists of a single element since ax = xa (a, x E G ) implies x - 1 ax = a.

Exa m ple 14 Suppose we try to find the conjugacy classes in our favourite group of six ele­ ments with Cayley table as given above. One class is { e }. The class containing a is { e - 1 ae, a - 1 aa, b- 1 ab, c- 1 ac, d- 1 ad, f- 1 af} which is, in fact, {a, a, a, b, b, b} = {a, b } . The class containing c lt { e} u {a, b } is {e- 1 ce, a - 1 ca, b- 1 cb, c- 1 cc, d- 1 cd, f - 1 cf} which is {c, d, J, c, J, d} = {c, d, f} . The group is therefore partitioned into the three conjugacy classes, { e } , {a, b } and { c, d, ! } .

Defi nition 11 The element a i n G is said t o be self-conjugate or central if x- 1 ax = a for all x E G. The set of central elements is called the centre of G and is denoted by Z(G ) . Notice that e E Z(G) and that Z(G ) = G i f and only if G is Abelian.

Groups, Rings and Fields

114 Exercises 4. 2

1 . Let S = { 0 } U N. Under the operation of addition is S a group?

2. Prove that the identity e of a group G is the only element of G satisfy­ ing the equation x2 = x (x E G ) . 3. Let a, b, c, d E G. Simplify ( ab2 ) - 1 (c2 a- 1 ) - 1 ( c b2 d) (ad) - 2 a,

(abc) - 1 ( ab? d( d - 1 b- 1 ) 2 bdc.

4. It is asserted that a group G of order 5, G following Cayley table

=

{ e, a, b, c, d } , has the

e

a

b

c

d

e

e

b

c

d

a b

a

a c

d

e

b

b

d

e

a

c

c

c

b

a

d

e

d

d

e

c

b

a

Is the assertion correct? 5.

In

forming the Cayley table of the non-Abelian group of order 6 (Examples 1 1 no. 3) , only three of the 36 products were actually evaluated. Verify the following equations (note omission of o ) . ab = e , ca =

J,

{

= d,

be = J,

bf = d ,

= e,

cf = a ,

db

fb = c ,

ff = e.

ac

cc

=

J,

}

2k� 2k� IkEZ . cos 3 + i sin J Prove that S is a multiplicative group of order 3.

6. Let S =

{

7. Prove that the set of complex numbers S=

. 2h 2k� cos ---;- + i sm ----;- I k E Z

}

is a cyclic group of order n. 8 . A mapping f : [0, 1] -+ [0, 1] , where [0, 1] is the closed interval of ana­ lysis { x I 0 ::; x :::; 1 }, is said to be strictly monotonic if the inequalities 0 :::; x 1 < x 2 :::; 1 imply that f (x l ) < f(x 2 ) . Under the circle composi­

tion of mappings prove that the set of strictly monotonic mappings of [0, 1] into [0, 1] is a group.

I ntroduction to Groups

115

(

9. Prove that the set G of matrices of the form

a b -b a

)

(a, b E IR, a2 + b2 ::/; 0)

is a group under matrix multiplication. What is the centre of this group? 1 0. (Hard) Like an example above, this problem originates in the physi­ cal world. Let c be a given strictly positive constant. (i) Let u , v E R be such that l u i < c, l v l < c. Prove that l w l < c where

u+v w = -----uv · 1 + ­2 c

[

) 'R2

(ii) Let X = { (x, t) l x, t E IR} . For each v E IR we define a mapping Tv :

Tv(x, t) =

x - vt

R 1 --

Cl

Prove that

X -+ X by v

t - -x Cl • 1 --

Cl

Deduce that the set S of such mappings is a group. This group is in fact the Lorentz group of transformations of relativistic mechanics (after H.A. Lorentz, 1 853-1 928) .

4.3 Subgroups

We have explored some immediate consequences of the definition of the group G. We now wish to look more closely at the structure of G and we begin by exam­ ining various sul:rstructures.

116

Groups, Rings and Fields

Defi nition 12 Let H be a non-empty subset of the group G which is also a group under the multiplication in G. Then H is called a subgroup of G. As for subrings, this definition is too descriptive to be useful. We give a convenient criterion.

Theorem 8 S u bgroup Criterion A non-empty subset H of the group G is a subgroup of G if and only if for all 1 a, b E H, ab E H and a- E H.

Proof Suppose H is a subgroup of G. Then H is closed under the multiplication in G and so for all a, b E H, ab E H. Now H has an identity J, say, and then an inverse a ' , say, in H l = f = fe and so e = f 1E H. Let a E H. Then a has 1 such that a'a = e. But a- exists in G such that a- a = e. Thus a- 1 = a ' E H. Conversely if for all a, b E H1 ab E H and a- 1 E H then H is evidently closed under the multiplication in G. This multiplication is associative in G and so in H. Let a E H. Then a- 1 E H and so e = aa- 1 E H. For a E H we have a- 1 E H and so, finally, H is a subgroup. D Two obvious subgroups of G are G itself and { e } .

Defi nition 13 The subgroup H of the group G is said to be a proper subgroup if { e } =I H and H =F G.

Exa m ples 15 1. Let a E G. Then H = {an I n E Z} is a subgroup of G. To see this observe that

typical elements of H are am and an . Then

and so H is a subgroup of G. 2. Under the usual multiplication, let G be the group Q \ {0} and let H be the 2 subset of G given as { u 1 u E Q \ {0} } .

I ntroduction to Groups

117

Then H is certainly a non-empty subset of G. Furthermore if a, b E H we have a = x 2 , b = y2 for some x, y E Q \ {0} . Then ab = x2 '1f = (x y) 2 and a - 1 = (x 2 ) - 1 = x - 2 ( x - 1 ) 2 =

Since (x y) 2 E H and (x - 1 ) 2 E H we may conclude that H is a subgroup. 3. The cyclic group G of order 4, G = { e, a, b, c } with Cayley table e

a a

b b

c

e

e

a b

a b

c

e

e

c

b a

c

c

b

a

e

c

has one proper subgroup, namely { e, c} . 4. Under matrix multiplication the set G of matrices of the form

(

) (� � ) � (�1 �1 ) , (�1 �), ( � �1 ) a b -b a

(a, b E lR, a2 + b2 ::j;0)

forms a group. The four matrices

form a subgroup of G.

Theorem 9 Let H and K be subgroups of the group G. Then HnK is a subgroup of G.

Proof We should observe first of all that HnK is indeed non-empty since e E H and e E K implies that e E H nK. Let a, b E H nK. Then a, b E H and so, as H is a subgroup, ab E H and a- 1 E H. Similarly ab E K and a- 1 E K. Thus ab E H nK and a- 1 E HnK from which we conclude that HnK is a sub­ group. D A simple adaptation of the proof above shows that the intersection of any col­ lection of subgroups is again a subgroup. However, we do not have what might be thought to be the analogous result for the union of two subgroups; we may note the following result in passing.

Groups, Rings and Fields

118

Theorem 10 Let H and K be subgroups of the group G. Suppose H U K is a subgroup of G. Then either H � K or K � H.

Proof For the sake of argument suppose that H is not a subset of K. Then there exists h E H, h ¢ K. We shall prove that K � H. Let a E K. Then a, h E H U K and, as H U K is a subgroup, ah E H U K. We then have two possible alternatives, either ah E H or ah E K. If ah E K and since a- 1 E K we would have h = a- 1 (ah) E K which is contrary to our choice of h. Thus ah E H and since h E H we have h - 1 E H and so a = (ah)h - 1 E H. Thus K � H. 0

Exam ple 16 Let D4 = { e, a, b , c, d, J, g, h} be the group of order 8 with Cayley table below. The group is called the dihedral group of order 8. e

a

b

c

d

f

g

h

e

e

b

c

d

f

a b

c

e

f

e

a

f

c

a

b

g h

d

c d

f

e

·<;

f

g h

f b

f

c e h d

g h

g h

h

a b

a b

a

e

c

g a b

b

c

c

a b

e a

e

g h

d g h

f

d

g h

g

f

d

d

d

G and { e} are, of course, subgroups. The remaining subgroups are { e, b} , { e, d} , {e, g} , { e , !} , { e , h} , {e, a, b, c} , { e, b, d, g } and { e, b , J, h } ; of these sul:r groups we may verify that the first six are cyclic and the last two are, struc­ turally, Klein four-groups. We now come to a particular and important type of subgroup.

Introduction

to

Grou ps

119

Lem ma 3 Let a be an element of the group G. Let the subset {x E G l x - 1 ax denoted by C0(a) . Then Ca(a) is a subgroup of G containing a.

= a}

be

Proof We observe first that Ca(a) is non-empty since a- 1 aa = a and so a E x, y E C0(a) . Then x - 1 ax = a and y- 1 ay = a. We have

C0(a) . Let

(xy) - 1 a(xy) = y- 1 x - 1 axy = y- 1 ay = a and so xy E Ca(a) . A lso from x - 1 ax = a we have a = xx - 1 axx - 1 = xax - 1 = (x - 1 )- 1 a(x - 1 ) , from which x - 1 E C0(a) . Thus Ca(a ) is a subgroup.

D

Defi nition 14 Let a be an element of the group G. Then C0(a) group called the centralizer of a in G. Since x - 1 ax = a if and only if ax all elements 'commuting' with a.

= {x E G l x- 1 ax = a} is a sub­

= xa, C0(a) is the subset of G consisting of

Theorem 1 1 The centre Z( G) of the group

G is a subgroup of G.

P roof We may follow the argument of Lemma 3. We have

Z(G ) = {x E G l x - 1 ax = a for all a E G } . Thus if x, y E Z( G) then x, y E C0(a) for all a E G and xy, x - 1 C0(a) for all a E G. Thus xy, x - 1 E Z(G) and so Z(G) is a subgroup. D so

Defi nition 15 Let X and Y be non-empty subsets of the group G. Let XY be the subset given by XY

= { xy I x E X, y E Y} .

Groups, Rings and Fields

120

Similarly XYZ , written without brackets as multiplication is associative, denotes the subset given by XYZ

= {xyzi x E X, y E Y, z E Z}.

If, in particular, X and Z are each subsets of a single element, X = { x } and Z = {z} , say, then xY is to be written for {x}Y and xYz is to be written for {x}Y{z} . Thus xY = {xy i y E Y}, Yz = {yz i y E Y} . We note that if A , B, X, Y are subsets of G such that A � B then evidently We remark that for a subgroup H of the group G we have necessarily

XAY � XBY.

hH = Hh H for all h E H. =

Lem ma 4 Let H be a subgroup of the group G and let x by {x - 1 hx l h E H } is a subgroup of G.

E G. Then the subset x - 1 Hx given

Proof Let

a , b E x - 1 Hx. Then there exist h , k E H such that a = x - 1 hx,

But and since

(X - 1 h - 1 X )( a ) (X - 1 h - 1 X )( X - 1 hX ) = X - 1 h - 1 XX - 1 hX = X - 1 h - 1 hX = X - 1 X = e . But H is a subgroup and so hk, h - 1 E H. Thus ab, a- 1 E x - 1 Hx which is there­ =

fore a subgroup.

D

Defi n ition 16

H be a subgroup of the group G. Any subgroup of the form x - 1 Hx for some x E G is called a conjugate of H. A subgroup H which coincides with all its con­ Let

jugates is said to be normal in G.

I ntroduction to Groups

121

Thus H is normal in G if and only if x - 1 Hx = H for all x E G or, equivalently, xH = Hx for all x E G. A useful characterization of normality is given in the next result.

Theorem 12 Let H be a subgroup of the x - 1 Hx � H for all x E G.

group G. Then

H

is

normal in G if and only if

P roof Certainly if H is normal in G the condition holds by definition. Suppose now x - 1 Hx � H for all x E G. We want to show that H � all x E G. Now x - 1 Hx � H implies that

x(x - 1 Hx )x - 1

�

x - 1 Hx for

xHx - 1

and so This proves the result.

D

Normal subgroups are usually easier to determine than subgroups which are not normal. The centre of a group is always normal and all subgroups of an Abelian group are normal.

Example 1 7 I n the dihedral group D4 of order 8 in Example 1 6 , the centre Z(D4 ) is To see this we observe that

b - 1 ab = bab = cb = a b- 1 cb = bcb = ab = c b - 1 db = bdb = gb = d, '

'

etc.

The remaining subgroups of order 2 are not nonnal since, for example,

a- 1 {e, d} a = {a- 1 ea, a - 1 da } = {e, g}. The subgroups of order 4 are all normal since we have

a - 1 {e, b, d, g}a = {a - 1 ea, a- 1 ba, a - 1 da, a- 1 ga} = {e, b, g, b}

etc.

{ e, b } .

Groups, Rings and Fields

122

We have proved that the subgroups {e, d} and {e, g} are conjugate and we may prove that { e, !} and { e, h} are conjugate. Any two distinct four-element subgroups have { e, b } as their intersection. We note, for future reference, that

{e, d} {e, g} = {e, b, d, g} = {e, g}{e, d}, but

{ e, d} { e, !} = { e, c, d, !} =I { e, a, d, !} = { e, /}{ e, d} . Theorem 13 Let H and K be normal subgroups of the group G. Then H n K is a normal sub­ group of G.

Proof We have already shown that H n K is a subgroup of G. We merely have to estab­ lish the normality of H n K in G. Let x E G. Then from H n K � H we have x - 1 (H n K ) x � H. Similarly x - 1 (H n K)x � K. Thus x - 1 (H n K)x � H n K and so H n K is normal in G. D

Lem ma 5 Let H be a subgroup of the group G. Let Na(H) denote the subset of G given by {x E G l x - 1 Hx = H}. Then Na (H) is a subgroup of G containing H.

P roof

x, y E Na(H) . Then x - 1 Hx = H and y- 1 Hy = H. Hence (xy) - 1 H(xy) = y- 1 x - 1 Hxy = y- 1 Hy = H and so xy E Na(H). Also H = eHe = (x - 1 ) - 1 x - 1 Hxx - 1 = (x - 1 ) - 1 H(x - 1 ) and x- 1 E Na(H). Thus Na(H) is a subgroup.

Let

so

D

Defi n ition 17 Let H be a subgroup of the group G. Then Na(H) subgroup called the normalizer of H in G.

= {x E G l x - 1 Hx = H} is a

I ntroduction to Groups

123

Na(H) is the largest subgroup of G in which H is Na(H) = H if and only if H is a normal subgroup of G.

a normal subgroup.

Theorem 14

N be subgroups of G and let N be a normal subgroup of G. HN = NH and HN is a subgroup of G.

Let H and

Then

P roof First we prove that HN = NH. We observe that HN consists of all elements of the form hn ( h E H, n E N ) and moreover that each such element belongs to NH since hn = (hnh - 1 )h E NH as N is normal in G, thus HN � NH. Similarly NH � HN and so NH = HN. Suppose now a, b E HN. Then there exist h 1 , h2 E H and n 1 , � E N such that a = h 1 n 1 and b = h2 n2 • Then

ab = h1 n 1 h2 � = h t (nt �n1 1 )n 1 n2 E HN

since N is a normal subgroup and H is a subgroup and

a- 1 = (h 1 n t ) - 1 = n1 1 h1 1 E NH = HN.

Thus HN is a subgroup of G.

D

Exa mples 18

= D4 of order 8 as above, suppose we wish to find Na ( {e, d} ) . Reading from the Cayley table, we have e - 1 de = d, a- 1 da = g, b- 1 db = d, c- 1 dc = g, d- 1 dd = d, r 1 df = g, g- 1 dg = d, h - 1 dh = g. Thus Na({e, d}) = {e, b , d, g}.

1 . In the dihedral group G

Alternatively we may observe that and so

Na({e, d}) Na({e, d})

;2

;2

Z(D4)

= {e, b }

{e, d}{e, b } = {e, b, d, g}.

But

Na({e, d}) # D4 as

{ e, d} is not normal and we already know all subgroups of D4 so that Na({e, d}) = {e, b , d, g}.

Groups, Rings and Fields

124

Similarly we have 2.

NG {{e, g}) = {e, b, d, g}, NG { {e, f}) = {e, b, /, h}. We recall that a square matrix A over lR is non-singular if A - 1 exists, equivalently if A has non-zero determinant. In the case of a 2 x 2 matrix

or

A is non-singular if and only if ad - be ::j; 0 and then d -b 1 a- 1 = ad - bc a · -c

)

(

The set of such non-singular 2 x 2 matrices over lR forms a group under multi­ plication which is called the general linear group of 2 x 2 matrices over 1R and which is denoted by GL{2, 1R) {for the proof that GL(2, 1R) is a group see Exercises 4.3, no. 6 ) . Suppose w e want t o find the centre Z(GL(2, IR) ) . Then w e are looking for all matrices

( xz yt )

such that

(xt - yz =I 0)

for all a, b , c, d E IR, ad - be =I 0. Instead of considering arbitrary a, b, c, d we notice that the above has certainly to hold for particular choices of non-singular matrices such as

(� � )

and

Now

implies

( xz

from which X

=

X

+

Z,

( � �) .

) (

x+y x+z y+t = z+t z t X+y=

y + t and

SO Z

=

)

0, X

= t.

I ntroduction to Groups

Similarly from

125

( � � ) we obtain y

=

0,

x = t. Thus for

� (: ) to be in the

centre we must have

But, on the other hand, we always have

Hence the centre Z ( GL ( 2, IR) ) consists precisely of the so-called 'scalar matrices'

( � � ) where x # 0.

We claim that

( : � ) such

is an Abelian subgroup of GL ( 2, 1R) . (For proof see Exercises 4.3, no. 6) . Suppose we want to find Na(H) . Then we require to find those matrices that

for all a E JR. Consequently, we require to find those matrices given

) ) ( : � ( � ; ) (: � ( � � )

a E lR there exists b E lR such that -1

=

or, equivalently,

Thus we must have

( x +z az

y + at t

) ( xz =

bx + y bz + t

)

from which and

so

x + az = x, y + at = bx + y, t = bz + t az = bz = 0, at = bx.

(:

�)

for which

Groups, Rings and Fields

126

Since

a is arbitrary, z = 0. But now,

(� � )-l ( � ;) (� �) (xt # O) = :t ( � �y) ( � ; ) ( � �)

( ) (1 �). 1

2a .!_ = = xt tx t 0 xt

Thus finally

0

We have defined the centralizer of an element and the normalizer of a sub­ group. We may extend the definitions very slightly as follows.

Defin ition 18 Let A be a non-empty subset of the group G. The centralizer and the normalizer of A are defined to be the subgroups C0(A) and N0(A ) given respectively by

Ca(A) = {x E G l x- 1 ax = a for all a E A}, Na(A) = {x E G l x- 1 Ax = A }.

We have asserted that these subsets are subgroups and the assertion should be confirmed. We have

Ga(A) = and,

n Ca(a),

4EA

in particular, Z( G ) = Ca(G) =

n Ca(a) .

BEG

Exercises 4.3

1. Write down the Cayley table of a cyclic group proper subgroups of G.

G of order 6. Find the

2. Let {A, B, C, . . . } be a set of subgroups of a group intersection A n B n C . . . is a subgroup of G.

G.

Prove that the

I ntroduction to Groups

127

3. Find the subgroups of the non-Abelian group of order 6 in Examples 1 1 no. 3 and Example 14. Determine which are normal. Determine the conjugates of each subgroup. 4. Let {A, B, C, . . . } be a set of normal subgroups of a group G . Prove that A n B n C n . . . is a normal subgroup of G. 5. Let H be a subgroup of the group G and let a E G. Prove that a - l Ha is a subgroup of G and that

is a normal subgroup of G . 6. Prove that the set GL(2, R) of non-singular 2 and that

x

2 matrices is a group,

is an Abelian subgroup.

A be a non-empty subset of the group G. Prove that normal subgroup of Na ( A )

7. Let

Ca(A )

is a

8. (Hard) We have shown that if N and H are subgroups of G and N is a normal subgroup then NH is a subgroup of G and NH = HN. With­ out assuming that N is a normal subgroup prove that NH is a sub­ group if and only if NH = HN. 9. (Hard) Let G be a finite group and let H be a proper subgroup of G and let H have n conjugates H = H1 , H2 , . . . , Hn . Prove that the set H1 U H2 U . . . U Hn contains, at most, n( I H I 1 ) + 1 elements of G. Deduce that G is not equal to the union H1 U H2 U . . . U Hn . -

4.4 Lagrange's Theorem, Cosets and Conjugacy We shall consider two partitions of G. The first will be obtained from 'cosets' of a subgroup of G and the second from the conjugacy of elements of G.

Defi nition 19

a E G. Then aH = {ah i h E H}

Let H be a subgroup of the group G. Let

Groups, Rings and Fields

128

is called the left coset of H in G determined by a. Similarly =

Ha {ha l h E H} is called the right coset of H in G determined by a. We note that a E Ha and that aH = Ha for all a E G if and only if H is normal in G. We shall prove a number of results on right cosets; it will be evident that analogous results will also hold for left cosets.

Theorem 15 Let H be a subgroup o f the group G. Let a, b E G. Then the following statements are equivalent . 1 . Ha = Hb. 2. There exists

3. 4.

b E Ha. ba- 1 E H.

h E H such that b = ha.

P roof We prove the equivalence of the statements in a cyclic manner. Suppose 1 holds. Then from Ha = Hb we have b E Hb = Ha and so there exists h E H such that b = ha. Thus 2 holds. Suppose 2 holds. Since b = ha for some h E H we have, by definition, b E Ha and 3 holds. Suppose 3 holds. From b E Ha we have b = ha for some h E H and so, evidently, ba - 1 = haa- 1 = h E H. Thus 4 holds. Suppose 4 holds. Then ba- 1 E H implies Hba- 1 = H and so Hb = Hba- 1 a = Ha. This completes the proof. D

Theorem 16 Let H be a subgroup of the group G. Any two right cosets of H in G are either equal or have empty intersection. Consequently the set of right cosets of H in G is a partition of G.

Proof Let a, b E G. We have to show that either Ha = Hb or HanHb = 0. Suppose HanHb =/; 0, then we prove that Ha = Hb. Since HanHb f; 0 there exists

I ntroduction to Groups

129

x E Ha n Hb. Hence there exist h 1 , h2 E H such that x = h 1 a = h2 b. But then b = h2 1 h2b = h2 1 h 1 a where h2 1 h 1 E H as H is a subgroup. But then by Theorem 15 Ha = Hb. G is certainly the union of the cosets of H in G since each element x (say) of G belongs to the coset Hx in G. But Hx is also the only coset to which x belongs since if we find that x E Hy then necessarily Hx = Hy. Thus we may conclude that the set of right cosets of H in G is a partition of G. D

Exa mple 19 Consider the dihedral group D4 of order 8 (Example 16 and 1 7) . H = { e, !} is a subgroup. a ¢ { e, !} and { e, !} a = { ea, fa} = {a, d}. Choose b, b ¢ { e , !} U {e, f } a, then { e, !} b = {eb, fb} = {b, h}. Choose c ¢ {e, f} U {e, !}a U {e, f}b and then we obtain G = { e, !} U { e, !}a U { e, f } b U { e, f}c, which expresses G as a union of four mutually disjoint right cosets of H in G.

Defi n ition 20 Let H be a subgroup of the group G. If G is written as a union of mutually dis­ j oint right (left) cosets of H in G then G is said to be written as a right (left) coset decomposition of H in G. If there is an infinite number of cosets in a right (left) coset decomposition then H is said to have infinite index in G. If there is a finite number of cosets in a coset decomposition then H is said to have finite index equal to this number of cosets; we denote this number by I G : H I · At first glance it might appear that the index could depend on whether we were using right or left cosets. However, if we have a right coset decomposition G

= Ha 1 U Ha2 U . . . U Han

then we also have a left coset decomposition, namely, G

=

a 1 1 H u a2 1 H U . . . u a;; 1 H.

(For proof of this observation see Exercises 4.4, no. 2). Commonly we take a 1 and so Ha 1 is the subgroup H.

=

e

Lemma 6 Let H be a finite subgroup of G. Then the number of distinct elements in any coset of H is precisely the number of elements in H.

Gro ups, Rings and Fields

130

P roof Let a E H. Consider Ha. We have to prove that H and Ha have the same number of elements. We claim that the mapping f : H -+ Ha given by

f(h) = ha ( x E H). is a bijection. Certainly f is a surjection and f ( hi ) = f(h2 ) (h 1 , h2 H) implies that h 1 a = h2 a and so h1 = h2 , giving f as an injection. This completes the proof.

D

We now prove one of the seminal theorems in group theory. This theorem is named after J.-L. Lagrange ( 1 736-1 813) who, in effect, proved what we would now regard as a special case of the theorem.

Theorem 17 Lagra nge's Theorem Let H be a subgroup of the finite group G. Then the order of H divides the order of G and, in fact, I G I = I G : H I I H I .

Proof The group G may be written as a coset decomposition of the cosets of H in G. Suppose I G : H I = n. Then we have, say, G

=

Ha 1 U Ha2 U . . . U Han , , Han are distinct. By Lemma 6 the number of ele­

where the cosets Ha 1 , Ha2 , ments in each coset is I H I and there are n such cosets. The number of elements in G is I G I and so • • •

IGI = niHI = IG : HI IHI

giving the result.

D

Remark H H and

and

so

K are subgroups of the finite subgroup G where H k K k G then I G : H I I H I = I G I = I G : KI I KI = I G : KI I K : H I I H I IG : HI

=

IG : KI IK : HI .

I ntroduction to G roups

131

Exa m ples 20 1. Let the order of G be a prime p. Then G has only the subgroups G since if H is a subgroup of G, I H I divides p and so I H I = p or giving the result .

and { e } IHI = 1

2. We have listed the subgroups of the dihedral group D4 of order 8. Note that all subgroups are of orders 1 , 2, 4 or 8.

3.

It is fairly easy to prove that Z, considered as an additive group, has the subset 6Z = { 6x I x E Z} as a proper subgroup. The integer a belongs to the coset 6Z + a = {6x + a l x E Z } and a and b (b E Z ) belong to the same coset if and only if 6Z + a = 6Z + b. Thus a and b belong to the same coset if and only if a - b E 6Z or 6 divides a - b. The six cosets of 6Z are

6Z, 6Z + 1, 6Z + 2, 6Z + 3, 6Z + 4, 6Z + 5.

We now prove a result on cyclic groups which depends on the Division Algorithm for integers.

Theorem 18 An element of order and conversely.

n

of a group G generates a cyclic subgroup of order

n

of G,

P roof 2 Let a E G and suppose a has order n. Then e, a, a , , an - 1 are distinct and n m a = e. Let H = { a I m E Z} . Then H is the cyclic subgroup generated by a. Consider now a typical element am of H. By the Division Algorithm for integers there exist q, r E Z, 0 ::; r < n, such that • • •

m

= qn + r.

Then am = aqn + r = aqn ar = ( an ) q ar = e qar = ear = ar . Thus H = { e, a, . . . , an - 1 } and so a generates a cyclic subgroup of order n . Conversely if H is a cyclic subgroup of G of order n then H is generated by an element a of order p (say) . But an element a of order p generates a subgroup of order p and so, as H has order n, we must have p = n, thereby completing the proof. D

Groups, Rings and Fields

132

Theorem 19 A finite cyclic group G has subgroups of all possible orders.

Proof Suppose G has order n. Then by Lagrange 's Theorem any subgroup must have order m where m divides n. We wish to show that a subgroup of order m exists. Let m = nd ( d E N) . Let G be generated by a and let H be generated by ad ,

H = { ( ad n r E Z}. Now ( ad ) m = amd = a = e and e, ad , a2d , . . . , a( m- l ) d are d1" stmct s1 nce a has order n = md. Thus ad has order m and by Theorem 18, ad generates a sub­ m. group, namely H, of order D n

so ,

·

·

We now turn to the second of our partitions on the group G. We recall that if

a, b E G then a is conjugate to b if there exists x E G such that x - l ax = b and

that we proved that conjugacy is an equivalence relation on G (Theorem 7) ; this equivalence relation yields our partition of G.

Defi n ition 21 Let a be an element of the group G. The set of all elements of G conjugate to namely {x - 1 ax l x E G}, is called the conjugacy class of G containing a.

a,

The group G is therefore the disjoint union of its conjugacy classes. We now give a formula for the size of a finite conjugacy class in G.

Theorem 20 Let a be an element of the group G. Suppose the centralizer of a in G, C0(a) , has index n in G. Then a has precisely n conjugates.

Proof Let

Ca(a)x l U Ca(a)x2 U . . . U Ca(a)xn be a coset decomposition of C0(a) in G. We claim that the conjugates of a are G=

precisely

I ntroduction to Grou ps

133

Certainly if x E G then x belongs to some coset, say x = and some xk (l $. k $. n ) . Then

cxk for some c E Ca(a)

x - 1 ax = (cxk) - 1 a(cxk) = xk" 1 c- 1 acxk = xj; 1 axk. Thus the conjugates of a are x1 1 ax l > x2 1 ax 2 , . . . , x;;- 1 axn. We now have to show that these conjugates are distinct. Suppose for some i , j

x;- 1 ax; = xi- 1 axi.

Then and so

(x;xj 1 ) - 1 a(x;xj) = a. But this implies that x;xj 1 E C0( a) and hence x; and xi belong to the same coset of C0(a) in G. This is impossible unless i = j. Hence we obtain the result. D Corollary Let a be an element o f the group G. Then the number o f elements i n the conjugacy class of a divides I G I ·

P roof The number is I G :

Ca(a) l which, by Lagrange's Theorem, divides I G I .

D

Exa m ple 21 Suppose we try to find the conjugacy classes in the dihedral group D4 of order 8 . Since Z(D4) = { e, b} , { e} and {b} are two conjugacy classes . Consider the ele­ ment a of D4 . We need to find C0(a ) . We notice that {e, a , b, c} is an Abelian subgroup of G and so {e, a , b, c} � Ca(a) . This implies that 4 divides I Ca(a) l which, of course, divides 8. Thus I C0(a) l = 4 or 8. But I C0(a) l = 8 implies that a E Z(D4) which is false. Thus I Co( a) I = 4 and so Ca(a) = {e, a, b, c}. A suitable coset decomposition is G = Co( a) U Ca(a)d 1 and so {a, d- ad} = { a, c} is a conjugacy class. The centralizer C0 (d) of the element d is { e, b, d, g} and the conjugacy class containing d is { d, g} . Similarly

Groups, Rings and Fields

134

we may calculate the remaining conjugacy classes and so finally obtain as the conjugacy classes of D4, {e}, {b} , {a, b}, {d, g} and { f, h}. Exercises 4. 4

1 . In the same way that we proved that the number of conjugates of an element of a group G is the index of the centralizer of that element in the group G, prove that if a subgroup H of G has n conjugates in G then the normalizer, Nc(H) , has index n in G. 2. If

Ha 1 U Ha 2 U . . . U Han is a right coset decomposition of a subgroup H in the group G, prove G=

that

a -1 1 H u a2- l H U . . . U an- l H is a left coset decomposition of H in G.

3. What are the cosets of 1 2Z = the additive group Z?

{ 12x l x E Z} considered as a subgroup of

4.5 Homomorphisms We are here concerned with mappings which preserve algebraic structure. Such mappings are called 'homomorphisms' (Greek: homo same, morph form) . More precisely we have the following definition which we make for semigroups.

Defi n ition 22 :

f S -+ T be a mapping such that f(xy) = f(x)f(y)

Let S and T be semigroups and let for all

x, y E S. Then f is said to be a homomorphism from S into T.

Lem ma 7 Let S and T be semigroups and let f : S -+ T be a homomorphism. Then f( S ) a semigroup (strictly f ( S ) is a subsemigroup of T ) .

is

I ntroduction to Groups

135

P roof = a,

a,

b E f(S) . Then there exist x, y E S such that f(x) ab = f(x)f(y) = f(xy) E f(S). Thus f(S) is closed under multiplication and, since f(S ) multiplication is associative. Thus f(S) is a semigroup. Let

f(y) = b. Thus

is a subset of T, the D

For the remainder of this chapter we shall be concerned with homomorphisms of groups.

Theorem 21 Let G and H be groups and let f ing hold.

:G

--+

H be a homomorphism. Then the follow­

1 . If ea and

2. 3. 4.

en are the identities of G and H respectively, then f(ea) = en. For all x E G, [f(x)r 1 = f(x - 1 ) where [f(x)r 1 is the inverse of f(x) in H and x - 1 is the inverse of x in G. f(G ) is a subgroup of H. Let K {x E G l f(x) = en}. Then K is a normal subgroup of G. =

P roof We note the necessity of distinguishing the identities in the two groups G and H.

f(ea)f(ea) = f(eaea) = f(ea), we conclude that f(ea) = en. Since f(x - 1 )f(x) = f(x - 1 x) = f(ea) = en (x E G), we have f(x - 1 ) [f(x) r 1 . By Lemma 7, f(G) is closed under multiplication in H. Let now E f(G) . Then = f(x) for some x E G and - 1 = [f(x)r 1 = f(x - 1 ) E f(G). Thus f(G) is a subgroup of H. Since f(ea) = en, K is non-empty. Let x, y E K, then f(x) = f(y) = en.

1 . Since

2. 3.

4.

=

a

a

a

Hence

f(xy) = f(x)f(y) and

=

enen = en.

Groups, Rings and Fields

136

Consequently K is a subgroup of G. To prove that K is a normal subgroup let a E K, x E G. Then f(x - 1 ax) = f(x - 1 )f(ax) = f(x - 1 )f(a)f(x) = [f(x) r 1 eH f(x) = [f(x }t 1 f(x) = eH, and so x - 1 ax E K. Hence K is a normal subgroup of G. D

Defi nition 23 Let G and H be groups and let f : G --+ H be a homomorphism. Then the sub­ group K = { x E G I f(x) = eH} is a normal subgroup of G which is called the kernel of j, written Ker f.

Exa mples 22 1 . Let G be a group, G =I { e} . Then we always have at least two homomorph­ isms. First we have the mapping j, easily checked to be a homomorphism, given by f(x) = e (x E G) . Second, we have the mapping g defined by g ( x) = x ( x E G) , again easily verified to be a homomorphism. 2. Let G be the cyclic group of order 4 generated by a, G = { e 0, a, a2 , a3 } and a4 = e0. Let H be the cyclic group of order 2 generated by b, H = { eH, b} , b2 = eH· Then we assert that the mapping f : G --+ H given by

f(ea) = eH , f(a) = b, f(a2 ) = eH, f(a3 ) = b

is a homomorphism. We require to establish this assertion. For example we have We may similarly verify the other possibilities. 3. Let C \ {0} and lR \ {0} be the multiplicative groups of non-zero complex and real numbers respectively. Then the mapping f : C \ {0} --+ lR \ {0} given by

f(z) = l z l (z E C \ {0}) is a homomorphism since, by a property of the modulus (absolute value) of complex numbers, we have 4. Consider the non-Abelian group G of order Example 6 no. 3. Define p : G --+ { 1 , - 1 } by

p(e) =

1,

6 with

Cayley table given in

p(a) = 1 , p(b) = 1, p(c) = - 1, p(d) = - 1 , p(f) = - 1 .

I ntroduction to Grou ps

137

Then we may verify that p is a homomorphism, for example

p(df) = p(b) = 1 = ( - 1 ) ( - 1 ) = p(d)p(f) . 5 . The set G of matrices of the form

(

x Y o t

)

(x, y, t E IR, xt =I 0)

has been shown to be a group under matrix manipulation. We claim that the mapping f : G --+ lR \ {0 } given by f:

( � : ) --+ xt

(� ) ( )� �(

is a homomorphism. Certainly we have

��

x 1 Y1 0 t1

)

x2 Y2 � x 1 x 2 X1Y2 + Y1 t2 � = J� 0 t 1 t2 � 0 t2 = (x 1 x2 ) (t 1 t 2 ) = (x 1 t 1 ) (x 2 t 2 )

giving the result. (We note that

xt is the determinant of

(�

�),

see next

example) . 6. We have defined GL(2, IR ) as the group of non-singular 2 x 2 matrices. The mapping f : GL(2, 1R) --+ lR given by f(A) = det A, for any non-singular 2 x 2 matrix A , is a homomorphism since for 'square' matrices A and B, det(AB) = det A det B. 7. The existence of certain homomorphisms imposes conditions on the group or groups involved. For example, suppose the mapping f : x --+ x - 1 (x E G) is a homomorphism of the group G into itself. Then for x, y E G, and so

x - 1 y- 1 = f(x)f(y) = f(xy) = (xy) - 1 = y- 1 x - 1 ' yx = (x - 1 y- 1 ) - 1 = (y- 1 x - 1 ) - 1 = xy.

Thus if f is a homomorphism G is necessarily Abelian. Associated to each homomorphism of a group we have a normal subgroup called the kernel. Given a normal subgroup of a group we shall see that we may construct, from the cosets of the normal subgroup, another group onto which the original group may be homomorphically mapped with kernel equal

Groups, Rings and Fields

138

to the normal subgroup. We shall explore for a given group this tight relationship between groups onto which the given group may be homomorphically mapped and normal subgroups of the given group.

Lem ma 8 Let G and H be groups and let f : G --+ H be a homomorphism with kernel Let a and b be elements of G. Then f(a) = f(b) if and only if Ka = Kb.

K.

P roof

f(a) = f(b) . Then f(ab- 1 ) = f(a)f(b- 1 ) = f(a) [f(b)t 1 = f(b) [f(b) t 1 = eH · Hence ab- 1 E K and so Ka = Kb. Conversely if Ka = Kb then b = ka for some h E K and so f(b) f(ka) = f(k)f(a) = eH f(a) = f(a) . 0 Suppose

=

Theorem 22 Let H be a normal subgroup of the group G. Let G I H denote the set of cosets of H in G. A binary operation is defined on G I H as follows. Let Ha and Hb (a, b E G) be cosets of H in G and define (Ha) (Hb) = Hab. Then this binary operation is well-defined and under this operation G I H is a group. Further the mapping G --+ G I H given by a --+ Ha (a E G) is a homomorphism of G onto GIH with kernel H.

Proof It is not immediately obvious that the binary operation on G I H is well-defined. In order that the definition should be well-founded we have to show that if Ha = Ha' and Hb = Hb' (a, a', b, b' E G) then Hab = Ha'b'. Now under the assumption that Ha = Ha' and Hb = HI/ we have that a' = h 1 a and If = h2 b for some h1 , h2 E H respectively. Then

a'b' = h 1 ah2 b = h 1 a�a - 1 ab = hab where h = h 1 (ah2 a- 1 ) E H since H is a normal subgroup of G. Then Ha'll = Hhab = Hab

and so we have vindicated our claim that the definition is well-founded.

I ntroduction to Groups

139

We now show that G I H is a group. Certainly, by construction, G I H is closed under the defined multiplicative binary operation. Associativity follows easily since for a, b, c E G. (HaHb)Hc = HabHc = H(ab)c = Ha(bc) = Ha(Hbc) = Ha(HbHc) . The coset H plays the role of the identity element of G I H as HHa = HeHa = Hea = Ha (a E G ) . The inverse of Ha (a E G ) i s given by Ha- 1 since (Ha- 1 ) (Ha) = Ha- 1 a = He = H. Thus G I H is a group. The mapping f : G --+ GIH given by f(a) = Ha (a E G ) is obviously surjec­ tive and is a homomorphism since f(ab) = Hab = HaHb = f(a)f(b)

(a, b E G ) .

Finally Ker f = {a E G l f(a) = H} = {a E G I Ha = H} = H.

D

Defi nition 24 Let H be a normal subgroup of the group G. The group G I H, as constructed above, is said to be a factor-group of G. We note that if H has infinite index in G then G I H is infinite, whereas if H has finite index I G : H I in G then I GIH I = I G : H I .

Defi nition 25 Let G and H be groups and let f : G --+ H be a homomorphism. If f is surjective (!(G ) = H) then f is said to be an epimorphism (Greek: epi upon) . If f is injec­ tive (!(a) = f(b) implies a = b, a, b E G ) then f is said to be a monomorphism (Greek: mono alone) . If f is bijective (surjective and injective) then f is said to be an isomorphism (Greek: iso equal) .

Exa m p l e 23 The Klein four-group G

= { e, a, b, c} with Cayley table e a b c

e e a b c

a a e c b

b b c e a

c c b a e

( 01 10 ) ' ( -10 -10 ) ' ( 10 -01 ) ' ( -10 01 ) . 1 0 ) a --+ ( -1 0 ) e --+ ( 0 1 ' 0 -1 '

is isomorphic to the group H consisting of the four matrices

The isomorphism is given by the mapping

Isomorphic groups have the same grou�theoretical structure although they may differ in other material aspects.

Exa m ple 24 Consider the dihedral group D4 of order 8, the Cayley table of which we have used frequently. The centre Z(D4 ) { e, b} and since the centre is a normal sub­ group we may form the group D4 /Z(D4 ) . We shall see that this group is iso­ morphic to the Klein four-group. Let us denote the cosets of Z(D4 ) in D4 by capital letters. Thus let

=

E = Z(D4 ) = {e, b}, A = Z(D4 )a = {e, b}a = {a, ba} = {a, c}, B = Z(D4 )d = {e, b}d = {d, bd} = d, g} , C = Z(D4 ) j = {e, b}f = {f, bf} = {f, h}. We may now draw up a Cayley table for example

D4 / Z(D4 ) = {E, A, B, C } .

A 2 = Z(D4 )dZ(D4 )d = Z(D4 )d 2 = Z(D4 )e = E, AB = Z(D4 )aZ(D4 )d = Z(D4 )ad = Z(D4 )f = C,

For

I ntroduction to Groups

141

finally obtaining

E

A

B

c

E

E

A

c

A

A

E

B c

B

c

B c E

B A

c

B

A

E

which is the K lein four-group. We now come to the first of two important results in this section.

Theorem 23 First Isomorphism Theorem Let G and H be groups and let f : G Then GI K and H are isomorphic.

--+

H be an epimorphism with kernel K.

P roof The kernel K of the epimorphism f is a normal subgroup of G and so we also have an epimorphism g : G --+ GI K. Diagrammatically we have G

��

f

>H

G/K

What we want to do is to construct an isomorphism h from GI K to H. We cannot compose g with f. In a manner of speaking what we do is to reverse back­ wards along the arrow from GI K to G and go directly along the arrow from G to H. Once we have established that this process does yield a well-defined mapping h it is fairly easy to prove that the h so constructed is an isomorphism. Thus let Ka (a E G) be an element of GI K. We would like to define a mapping h : GIK --+ H by letting

h(Ka) = f(a) .

Groups, Rings and Fields

142

This definition only makes sense if Ka = Kb (a, b E G) implies that f(a) But Ka = Kb implies that b = ka where k E K and then

=

f(b) .

f(b) = f( ka ) = f(k)f(a) = eHf(a) = f(a). Consequently our definition is in fact soundly based. The mapping h is surjective since if c E H it follows that, as f is an epimorph­ ism, there exists a E G such that f(a) = c and then h(Ka) = f(a) = c. The mapping h is injective since if h ( Ka) = h(Kb) (a, b E G) then we have f(a) = f(b) and so f(ab- 1 ) = f(a)f(b) - 1 = eH from which ab- 1 E K and Ka = Kb. It remains now to show that h is a homomorphism. Let a, b E G, then

h(KaKb) = h(Kab) = f(ab) = f(a)f(b) = h(Ka)h(Kb). Thus finally we conclude that h is an isomorphism.

D

Exa m ples 25 1. Let G and H be groups and let f : G --+ H be a homomorphism. Then f( G) is a subgroup of H and f( G) is isomorphic to G I K. 2. Let G and H be finite groups and let f : G --+ H be an epimorphism. Then I H I divides I G I since

= I Ker f i i G : Ker f l = I Ker f i i GIK I = I Ker f i i H I . Let H be a subgroup of the centre Z(G) of the group G . Suppose GIH is cyclic. Then there exists a E G such that GIH = { (Hat l n E Z} . But (Hat = Han and so GIH = {Han l n E Z} . Now this fact implies that G is Abelian since if we have x, y E G then x = h1an , y = h2 am for some h1 , � E H and m, n E Z, and therefore, as H � Z(G), n n xy = ( h1a ) (�am ) = h h2 a am h2 h1am an = �am h1an yx. 1 IGI

3.

=

=

We now arrive at the second of our important theorems.

Theorem 24 Second Isomorph ism Theorem Let G be a group, let H and N be subgroups of G and let N be normal in G. Then the factor-groups NH IN and H I ( N n H) are isomorphic.

P roof Notice that since N is normal in G, NH is a subgroup and N n H is a normal subgroup of H. The following diagram may assist in the understanding of the statement of the theorem:

I ntroduction to Grou ps

143

N

H

Each subgroup is shown to lie above any subgroup which it contains. Such dia­ grams in group theory are sometimes called Hass e diagrams ( after H. Hasse , 1898-1979 ) . W e first define a mapping p : H --+ NHIN and show that this mapping p is an epimorphism. For h E H we define p(h) to be the coset Nh of N in the subgroup NH = { nh I n E N, h E H}. Certainly p is surjective. But p is also a homomorph­ ism since

p(h 1 h2 ) = Nh 1 h2 = Nh 1 Nh2 = p(h t )p(h2 ) (h b h2 E H). Thus p is an epimorphism. Let K = K er p. Then, by the First Isomorphism Theorem, HI K is isomorphic to NH IN. In order to complete the proof we have to prove that K = N n H. Let h E H n N. Then h E N and so Nh = N and thus h E K. On the other hand, if k E K then Nk = N, and so we have k E N and finally k E N n H. Thus K = N n H. 0 Some groups admit of only two epimorphisms, namely the epimorphism in which all elements of the group are mapped into the number 1 and the isomorph­ ism of the group with itself. Since the existence of epimorphisms is directly related to the existence of normal subgroups we make the following definition.

Defi nition 26 A non-trivial group which has no proper normal subgroups is said to be simple.

Exa m ple 26 Suppose w e consider a non-trivial group G which is both simple and Abelian. We recall that in an Abelian group all subgroups are normal. Hence our present group G has no proper subgroups. Let a E G, a =I e. Then a generates a non­ 2 trivial cyclic subgroup which must be G. If G is infinite then a generates a

Groups, Rings and Fields

144

proper subgroup and we would have a contradiction. Hence G is a finite cyclic group. Let p be a prime divisor of the order of G. Then G has a subgroup of order p which must be G itself. Hence, to summarize, a non-trivial simple Abelian group is cyclic of prime order. For obvious reasons the mathematical interest is in non-Abelian simple groups. Exercises 4.5

1 . Let G, H and K be groups. Let f : G -+ H and g : H -+ homomorphisms. Prove that g o f is a homomorphism.

K be given

2. Let G be a group and suppose that the mapping f : G -+ G, which is given by f (a) = a2 (a E G ) , is a homomorphism. Prove that G is Abelian.

3. Let G be a group with centre Z(G) . Suppose there exists a E G such 1 1 that x- a- xa E Z(G) for all x E G. Prove that the mapping 1 1 x -+ x- a- xa is a homomorphism of G into Z(G ) . 4. Let N and H be subgroups of the group G where N s; H s; G and N is normal in G. Prove that HI N is a subgroup of G and that every subgroup of GIN is of the form HI N for some subgroup H of G. Prove that HI N is a normal subgroup of GIN if and only if H is a normal subgroup of G.

5. The quaternion group Q of order 8 is given by Q

=

{ e, a, b, c, d, f, g, h}

with Cayley table e

a

e

e

a

b b

a

a

e

c

b

b

b

d d f

c

a

e

g

f f d h

c

c

e

a

h

g

d f

d f

g

g

h

h

b f d h g

h g

d f

c c

g

h f d

g g

h h

a

e

h f d b

e

a

c

c

b

b

a

e

b

c

e

a

g

d f c

What is the centre Z(Q) of Q? Find all subgroups of Q and construct a Hasse diagram. Determine the conjugacy classes. Identify the group QIZ(Q) .

5 Rings

We first formulated the abstract concept of a ring from our considerations of the integers and of polynomials. It is our aim to carry forward and to develop the concept of a ring, for which the integers will continue to serve as a useful exemplar.

5.1 Arithmetic Modulo

n

Let us , for the present, focus our attention on the prime 3 in the ring of integers z. Suppose we were to consider only the integers 0, 1 , 2. Ail it stands the set {0, 1 , 2} is not a ring since, for example, 2 + 2 = 4 ¢ {0, 1 , 2}. However, suppose we perform addition and multiplication 'modularly' with regard to the prime 3, that is to say we replace any sum or product of the numbers 0, 1 , 2 by the cor­ responding remainder on division by 3. Thus we would have

2 + 2 = 1 (mod 3) since 2 + 2 = 4 = 3 + 1, where to emphasise that we are performing 'addition' and 'multiplication' modularly we use the symbol = which denotes 'congruence' and we also write 'mod 3'. We may compile modular addition and multiplication tables as follows.

145

Groups, Rings and Fields

146

Swn 0 1 2

0 0 1 2

1 1 2 0

Product 0 1 2

2 2 0 1

0 0 0 0

1 0 1 2

2 0 2 1

AP. we shall shortly see {0, 1 , 2} with these tables becomes a ring. We now require to make rather more precise some of the notions above.

Defi n ition 1 Let n be a given non-zero integer. Let a and b be two integers. We say that a is congruent to b if n divides a - b. We write a = b (mod n). Otherwise we say that a is not congruent to b modulo n if n does not divide a - b.

Exam ple 1 Since 24 divides 48

=

83 - 35 we have 83 = 35 (mod 24) .

Since 17 does not divide 96 = 122 - 26 it is evident that

1 22 = 26 (mod 1 7) is false.

The next lemma summarises some obvious facts.

Lem ma 1 Let n be a given non-zero integer. Then the following statements hold.

1. For all integers a, a = a (mod n). 2. Let a and b be integers such that a = b (mod n) . Then b = a (mod n) . 3. Let a, b and c be integers such that a = b (mod n) and b = c (mod n) . Then a = c (mod n) . 4 . The relation of congruence is an equivalence relation on Z.

P roof Certainly n divides 0 = a - a for all integers a and so we obtain 1 . If for integers a and b, n divides a - b then n divides b - a, and 2 follows. To prove 3 we remark that if n divides a - b and n divides b - c then n divides a - c = (a - b) + (b - c) giving 3. Statement 4 is an immediate consequence of the three preceding statements. 0

147

Rings

By Lemma 1 , for a given non-zero integer n, the set of integers is partitioned into equivalence classes of integers. H a E Z the equivalence class containing a is

{x

E Z l x = a (mod n) } = {a + nk l k E Z}.

Notation For a given non-zero integer n the equivalence class of integers containing an integer a is denoted by a. a =

{ a + kn l k

E Z} .

Exa m ple 2 Let n

=

12 . Then

E Z} = { . . . - 20, -8, 4, 16, 28 , . . . } , 27 = {27 + 12k l k E Z} = { . . . , 3, 15, 27, 39, 51 , . . . } = 3. 4 = {4 + 12k l k

We have remarked in passing that abstraction often leads to greater insight. Our present approach to the concept of 'integers modulo n' has been direct but has taken no account of our existing knowledge. Suppose we reconsider 'integers modulo n' in the light of the group theory of the previous chapter. We see that Z is an additive group and that nZ = {nk l k E Z} is the cyclic sub­ group generated by n; the equivalence classes modulo n are precisely the cosets of nZ in Z. Now we may form the factor-group ZjnZ consisting of these cosets as elements and with addition in ZjnZ given by a

+ b = a + b (a, b

E Z) .

Notation The factor-group Z/nZ is denoted by Zn, where for definiteness we suppose that n > l.

Exa m ple 3 Zs

=

{o, I, 2, 3, 4, 5, 6, 7}

and, for example,

2 + 3 = 5, 5+6

=

TI

4 + 5 = 9 = I, =

3,

4 + 4 = 8 = o.

Groups, Rings and Fields

148

What is perhaps less obvious from these considerations is that we may also introduce a multiplication with regard to the equivalence classes modulo n in such a way that Zn becomes a ring. We summarise these facts in a theorem.

Theorem 1 Let n be a given integer, n > 1 . Then Zn, the set of equivalence classes modulo n , is a commutative ring with an identity under the definitions:

a + b = a + b (a, b E Z), ab = ab (a, b E Z). Proof We know that addition is unambiguously defined by a + b = a + b (a, b E Z) and that, under this addition, Zn is an additive group. To establish the multiplication we must first show that the rule of multiplica­ tion above is meaningful. In other words if a = a' and b = fl (a, b, a', b' E Z) then we have to prove that ab = a' b' . But a = a' implies that n divides a - a' and, similarly, n divides b - b'. But

ab - a'lf = (a - a')b + a' (b - If ) and so n divides ab - a'lf, consequently ab = a' b' . The associativity of the multiplication follows from the definition and the associativity of multiplication in Z since for a, b, c E Z we have

(ab)c = (ab)c = (ab)c = a(bc) = a(bc) = a(bc). In a similar manner the distributive laws hold since for a, b, c E Z we have a(b + c) = a(b + c) = a(b + c) = ab + ac = ab + ac = ab + ac. The other distributive law is equally easy to prove and so, finally, we conclude that Zn is a ring. Fairly obviously Zn is commutative and I is the identity since I

=

a la = a = al = ai (a E Z).

D

Exa mple 4 Following the above argument, let us write down the addition and multiplication tables of Z6 = {o , I, 2, 3, 4, 5 } .

149

Rings

Sum 0 I 2 3 4 5 0 I 2 3 4 5 0

I 2 3 2 3 4 3 4 5 4 5 0 5 0 I

I 2 3 4 5

4 5 0 I 2

0 I 2 3 4

5 0 I 2 3

Product 0 I 2 3 4 5 0 0 0 0 0 0 0

I 2

3

4 5

0 0 0 0 0

I 2 3 4 5

2 3 4 5 4 0 2 4 0 3 0 3 2 0 4 2 4 3 2 I

Although Z6 is a commutative ring with I as identity, Zs is not an integral domain since proper divisors of zero exist, for example, 2.3 = 0.

Exa m ple 5 Let

us

write down the addition and multiplication tables of Z5 Sum 0 I 2 3 4 0 1 2 3 4 0

I 2 3 4

I 2 3 4

2 3 4 0

3 4 0 I

4 0 I 2

0 I 2 3

=

{0, I , 2, 3, 4}.

Product 0 I 2 3 4 0 0 0 0 0 0 I

2 3 4

0 I 2 3 4 0 2 4 I 3 0 3 I 4 2 0 4 3 2 I

In this case there are no proper divisors of zero and Z5 is an integral domain. We notice that, in fact, the set of non-zero elements {I, 2, 3, 4} is a cyclic group under multiplication.

Exercises 5. 1

1 . Write down the addition and multiplication tables of Z2 ,

Z3 and Z4 •

2. Find solutions to the following congruences: 4x = 3 {mod 7) ,

5y = 4 {mod 1 1 ) ,

2z = 5 (mod 13) .

3. Let m 1 and m2 be coprime integers and let u 1 and � be integers such that Ut m 1 + �m2 = 1 . For any a l l a2 E Z prove that if x = � u 1 m 1 + a 1 �m2 then x = a1 {mod m t ) and x = � {mod � ) . (Version of the Chinese Remainder Theorem, from China, date uncertain but before 636 AD. )

Grou ps, Rings and Fields

150

D and E be integral domains. Let R be the Cartesian product D x E and let an addition and multiplication be defined in R by (d1 , e 1 ) + (� , e2 ) = ( d1 + � . e1 + e2 ) , (d1 , e 1 ) (� , � ) = (dl � • e 1 � ) ( d1 , � E D, e 1 , e2 E E). Prove that R is a commutative ring with an identity but that R is not an 4. Let

integral domain.

5. Let D be an integral domain and let x be an element of D such that 2 x = x. Prove that either x = 0 or x is the identity of D. 6. Any modern book has an International Standard Book Number (ISBN) given in the form:

a 1 - � a3 a4 - a5 ll(; a7 asag - a1 0 . For example 'Finite-Dimensional Vector Spaces' by P.R. Halmos (Springer-Verlag, 1974) has ISBN 0-387-90093-4 and 'A History of Algebra' by B.L. van der Waerden (Springer-Verlag, 1985) has ISBN 0-387-13610-X (where X = 10) . Verify that, in these two examples,

a1 + 2 � + 3 aa + 4 a4 + 5 as + 6as + 7ar + Bas + 9ag + 10a 1 0 = 0 (mod 1 1 ) . Try this congruence for the ISBN of any, randomly chosen, modern book.

5 . 2 Integral Domains and Fields As we have just seen, the rings Z5 and Zt, have very different properties. We wish

to characterize Zn, for general

n,

but first we require some definitions.

Defi n ition 2 Let R be a ring with an identity 1. An element a of R is said to be invertible, or to be a unit, if there exists b in R such that ab = ba = 1 . We write b = a - l and call b (if it exists) the inverse of a.

Exa m ples 6 1 . All non-zero elements of Q, lR and C are invertible. 2. Z has only two invertible elements, namely ±1.

Rings

151

3. Zc; has two invertible elements I and 5. 4. Z5 has four invertible elements I, 2, 3 and 4. The existence, or otherwise, of invertible elements in a ring leads us to consider a 'field'. Dedekind gave in 1871 a definition of a field considered as a subset of the complex numbers, but the abstract definition of a field is due to Weber. A significant stimulus to research in fields was given in 1 9 1 0 by E. Steinitz (1871 -1 928) .

Defi nition 3 A commutative ring with an identity in which every non-zero element is invertible is called a field (German, Korper; French, corps).

Exa m ples 7 1 . Q, lR and C are fields. 2 . Z5 is a field.

3. Z is not a field. A convenient means of remembering the axioms of a field is given by the following characterization.

Theorem 2 Cha racterization of a Field Let R be a non-empty set with two binary operations of addition and multi­ plication such that the following hold.

1 . R is an additive Abelian group. 2. R \ {0} is a multiplicative Abelian group. 3. The distributive laws hold. Then R is a field.

Theorem 3 Every field is an integral domain.

152

Groups, Rings and Fields

P roof Let F be a field. Then F is a commutative ring with an identity 1 . We have only to show that F has no proper divisors of zero. Suppose there exist a, b E F such 1 1 that ab = 0. Now as a ::/; 0 there exists a- such that a- a = 1 and so we may 1 1 1 write b = 1 b = (a- a) b = a- (a b) = a- 0 = 0. Similarly if b ::/; 0 we prove that a = 0. Hence we deduce that F is an integral domain. D AB we observed above, an infinite integral domain, such as Z, need not be a field. However, for finite integral domains, we have an explicit result.

Theorem 4 A finite integral domain is a field.

Proof Let D be a finite integral domain. To prove that D is a field we have to show that D \ {0} is multiplicatively a group. Certainly D \ {0} is closed under multi­ plication since x, y E D \ {0} implies that x and y are not proper divisors of zero and so x y ::/; 0 and hence xy E D \ {0} . hsociativity being evident, D \ {0} is a semigroup. We claim that D \ {0} admits cancellation. Thus suppose there exist a, b, x E D \ {0} and ax = bx . By Example 10 in Chapter 3, we deduce that a = b and so we have cancellation. We have already shown that a finite semigroup with cancellation is a group ( Theorem 3, Chapter 4) and so D \ {0} is a group and then D is a field. D

Theorem 5 ZP is a field if and only if p is a prime.

Proof Suppose p is not a prime. We show that proper divisors of zero exist in Zn . We have p = n 1 n 2 for some n 1 1 n2, E N where 1 < n 1 < n, 1 < n2 < n. Then n 1 ::/; 0, n2 ::/; 0 but n 1 n2 = n 1 n2 = p = 0. Thus ZP is not an integral domain. Suppose now that n is a prime. We may prove that ZP is a field by reversing the argument of the previous paragraph to show that ZP is an integral domain and then, from Theorem 4, we deduce that Zv is a field. However, it is perhaps more instructive to prove the result directly without invoking Theorem 4. We know that ZP is a commutative ring with an identity I. We have to show

153

Rings

therefore that the non-zero elements of Zp are invertible. Now we have Zp = {0, I, , p - 1 } . Let a be a non-zero element of zp , a E {1 , 2, ,p - 1} Then as p is a prime, a and p are coprime and, by the Euclidean Algorithm, there exist x, y E Z such that ax + py = 1 . Hence 0 0

0

0

0 0

.

l = � + py = ax + py = ax + py = ax + � = ax

and

so

a

has x as inverse. Hence finally Zp is a field.

D

Since ZP , p prime, is a field, ZP has some features in common with Q and JR. Some algebraic manipulations which are familiar in Q and lR may also be performed in zp .

Exa m ples 8 Suppose we try to solve, if possible, the following pairs of simultaneous linear equations over z7.

!} .

�x + 3y = 3x + y = 4

1.

We make the coefficients of x the same in both equations by multiplying the first by 3 and the second by 2 . Thus we obtain

�·! }

�-�X + �.3y = 2.3x + 2y = 2.4 giving

�} ·

�X + �y = 6x + 2y = 1

These equations are therefore inconsistent and no solution is possible.

�x + �y = � 4x + 5y = 4 ·

}

2.

4 .6 }

We then have

4.3x + 4.6y = 3.4x + 3.5y = 3.4 giving

�} -

�x + 3y = 5x + y = 5 Subtracting we have

Groups, Rings and Fields

154

So far we have used only ring-theoretic properties of Z7• Now we use the invertibility of non-zero elements of Z7. 2 has 4 as an inverse and so we have

4 .2y = 4.5 which yields

y = Iy = 6. Similarly we may show that x = 4. In the ring of integers Z we may form the sums

1, 1 + 1, 1 + 1 + 1, 1 + 1 + 1 + 1, and these sums are distinct, being respectively 1 , 2 , 3, 4, . .

.

On the other hand, in

Zn the corresponding sequence

I, I + I, I + I + I, I + I + I + I, repeats as we obtain

I, 2, . . . , n - 1 , 0, I, 2,

..

.

, n - 1 , 0, . . .

In the first case there is no integer n (n > 0) for which n1 = 0 but in the second case ni = 0. These two cases require to be appropriately distinguished.

Defi nition 4 Let R be a ring with an identity 1 . R is said to have finite characteristic if there exists an integer n (n > 0) such that 0=

1 + 1 + . . . + 1 (n terms)

or, equivalently, that 0 = nl . Otherwise R is said to have infinite or zero characteristic. (It may seem to be a trifle odd that in this situation the words 'infinite' and 'zero' are regarded as synonymous but such indeed is the case. ) Before relating this definition ancillary result.

to

integral domains we prove an interesting

Lem ma 2 Let R be a ring with an identity 1 . Let R have finite characteristic and suppose that n1 = 0 (n > 0) . Then for all elements a of R, na = 0.

P roof

na = a + a + . . . + a (n terms ) = 1a + 1 a + . . . + 1 a = ( 1 + 1 + . . . + 1 ) a (distributivity ) = (n1)a = Oa = 0.

D

Our main interest is in the characteristics of integral domains and fields.

Theorem 6 Let D be an integral domain with identity 1 and of finite characteristic. Then there exists a unique prime p such that p1 = 0.

P roof By assumption there exists an integer n (n > 0) such that n1 = 0. Let p be chosen to be the least such integer, p1 = 0. We claim that p is a prime. Suppose, for the sake of argument, that p is not a prime and let p = p 1p2 where

1

< P1 < p,

1

< P2 < p

(pl , P2 E N) .

Then

(p l 1) ( P2 1 ) = ( 1 + 1 + . . . + 1 ) (1 + 1 + . . . + 1) where we have p 1 terms in the first bracket and p2 terms in the second. Expand­ ing by distributivity and collecting terms we have p 1 p2 terms of the form 1 1 = 1 . Thus

But D is an integral domain and so p 1 1 = 0 or p2 1 = 0. But either conclusion contradicts the choice of p as least integer such that p1 = 0. Hence p is a prime and is unique. D

Defi nition 5 Let D be an integral domain with identity 1 and of finite characteristic. The least integer p such that p1 = 0 is a prime called the characteristic of D. D is said to be of prime characteristic.

Groups, Rings and Fields

156

Exa m ples 9

1.

Z, Q, IR, C are of infinite characteristic. For each prime p, Zp is of prime characteristic p . 2. In a field F of characteristic 2, addition and subtraction are the same! This apparently paradoxical result arises as follows. We have 2 a = 0 and so a + a = 0. But then a = - a. Hence b + a = b - a for all a , b E F. 3. A field which is finite necessarily has finite characteristic. But a finite field of prime characteristic p need not have p elements. The following tables exhibit a field E of characteristic 2 having four elements 0, 1 , a, (3 . Sum 0 0 0

1 a f3

1 a f3

1 1 0

f3 a

a a f3 0

1

f3 f3 a 1 0

Product 0

1 a f3

0 0 0 0 0

1 0

1 a f3

a 0

a f3 1

f3 0

f3 1 a

We notice that F {0, 1 } is a 'subfield' of E. The quadratic polynomial x 2 + x + 1 does not factorize in F[x] but does factorize in E[x] since =

x2 + (a + f3)x + a/3 (x + a) (x + (3) . We may also notice that E \ {0} = { 1 , a, /3 } is multiplicatively a cyclic group of order 3 generated by either a or (3 . x2 + x + 1

=

=

Defin ition 6 Let F be a non-empty subset of the field E which is also a field under the addition and multiplication in E. Then F is called a subfield of E.

Theorem 7 S u bfield Criterion A non-empty subset F of a field axioms of a field are satisfied.

E is a subfield of E if and only if the following

1. ( i ) F is closed under addition. (iv ) For all a E F, -a E F.

2. (i ) F is closed under multiplication. (iii) 1 E F. 1 (iv ) For all a E F, a # 0, a- E F.

P roof Certainly if F is a sub field the axioms above must be satisfied. On the other hand if the axioms above are satisfied then F is a subring and the remaining axioms for a field are satisfied in F since they are satisfied in E. Hence we conclude that F is a subfield of E. D In certain instances Theorem 7 may obviate some lengthy verifications of the axioms for a field. If we know that an algebraic structure is a subset of a field we may be able to establish more easily that the structure is actually a subfield.

Exa m ple 10 Let F = {a + bv'2 1 a, b E Q} . Then F is a non-empty subset of the field JR. To prove that F is a subfield we may utilize Theorem 7. 1 . (i)

Typical elements of F are a + sum is

bv'2 and c + dv'2 (a, b, c, d E Q) and their

(a + bv'2) + (c + dv'2) = (a + c) + (b + d) v'2 which is of the form q1 + q2 v'2 where q1 , q2 E Q. Thus addition in F is

closed.

2.

( iv) a + bv'2 E F implies - (a + bv'2) (i ) Let a, b, c, d E Q. Then

= (-a) + ( -b) J2 E F.

(a + bv'2) (c + dv'2) = (ac + 2bd) + (ad + bc)v'2 E F since ac + 2bd, ad + be E Q. Thus multiplication in F is closed. ( iii ) 1 = 1 + OJ2 E F. ( iv) Let a + bv'2 ::/; 0 (a, b E Q) . Then a and b are not both zero. But then a - bv'2 ::/; 0 since a - bv'2 = 0 would imply that a = b = 0 since we have earlier shown that v'2 ¢ Q. Then a - bv'2 a + bv'2 (a + bv'2) (a - bv'2) a - bv'2 = a (-b) rn = 2 a - 2b2 a2 - 2b2 + a2 - 2b2 v 2 E F.

(a + bv'2t 1 =

Thus, finally,

we

1

conclude that F is a subfield of JR.

Integral domains of finite characteristic have a version of the well-known binomial theorem which, on first encounter , is mildly amusing. We illustrate this first by means of examples.

Groups, Rings and Fields

158

Exa m ples 1 1 1 . Let D be an integral domain of characteristic 2 . Let a , b commutative, we may expand (a + b) 2 to give

E

D.

Then, as D is

a2 + ab + ba + b2 = a2 + 2ab + b2 a2 + b2 since 2 ab 2. Let D be an integral domain of characteristic 3. Let a, b E D. Then, commutative, we may expand (a + b) 3 to give (a + b) 3 = a3 + 3a2 b + 3ab2 + b3 = a3 + b3 • (a + b ) 2

=

=

=

0

.

as D is

These examples should suggest a general result which we now prove.

Theorem 8 Let D be an integral domain of prime characteristic p. Let

a, b E D.

Then

(a + b) P = aP + b P . Proof We have to use the so-called binomial theorem, namely

(a + b) P

=

aP + pa p - l b + p(

� ; 1 ) ap - 2b2 + . . . + bP .

A typical term in this expansion, other than the first or the last, is

p(p - 1 ) . . . (p - r + 1 ) ap - r br where 1 �

r

� p - 1 . Now

1 .2 . . . r

p(p - 1 ) . . . (p - r + 1 ) 1 .2 . . . r is a strictly positive integer and so 1.2 . . . r must divide p(p - 1 ) . . . (p - r + 1 ) . But p is a prime and p > r so none of 1 , 2 , . . . , r can divide p but each must divide the product (p - 1 ) (p - 2) . . . (p - r + 1 ) . In consequence (p - 1 ) . . . (p - r + 1 ) is an integer. Thus p divides 1.2 . . . r p(p - 1) . . . (p - r + 1 )

Hence

1 .2 . . . r

p(p - 1 ) . . . (p - r + 1 ) aP -r br = 0. 1 .2 . . . r

159

Rings Thus, finally,

0

Corollary Let D be an integral domain o f prime characteristic elements of D. Then

p.

Let

a1 , 11:!, . . . , an

be

Proof A simple induction argument gives the result. Thus suppose

for some k �

2. Then

(a 1 + a2 + . . . + ak+ l ) P = [(al + . . . + ak) + ak+ l ] P = (a 1 + . . . + ak) P + a1 + 1 The result is immediate.

0

We conclude this section with a result drawing together integral domains and fields. A finite integral domain is a field but an infinite integral domain may or may not be a field. Now from the integral domain of the integers Z we obtain the quotient field Q of Z by simply taking quotients of elements of Z to form the elements of Q; in a similar way we may form the 'quotient field' of any integral domain. From the numbers 1 , 2, 3, 4, . . . we form quotients such as � . � . � , . . . where we identify �. �. � , . . . and 2, f, � , . . . etc. As we are long accustomed to make such identifications no difficulty is experienced in their manipulation. On reflection we realise that we are regarding �. �. � , . . . as equivalent under some unstated equivalence relation. If, therefore, we are to consider an arbitrary integral domain, we must make more precise the nature of an implicit equivalence rela­ tion. Instead of 'quotients' of two elements we begin more properly with ordered pairs of elements and then we introduce an appropriate equivalence relation. From a given integral domain D we construct a field F in which the integral domain is 'embedded', that is there is a bijective mapping of D into F preserving addition and multiplication, for example Z is 'embedded' in Q. (A more precise definition of embedding will be given in a subsequent section. )

Groups, Rings and Fields

160

Theorem 9 Let D be an integral domain. Then D may be embedded in

a

field.

Proof Let G D x ( D \ {0 } ) . Then G is the set of ordered pairs (a, b) where a, b are elements of D, b =I 0. (We shall construct a field consisting of what, informally, =

�

are quotients - The proof will perhaps be more easily comprehended if the reader thinks of (a, b) as standing for

� .)

The proof is in three steps. 1 We claim that the relation "' on G given by (a, b) "' ( c, d) if and only if ad = be is an equivalence relation. Certainly (a, b) "' (a, b) and if (a, b) "' ( c, d) we have ad = be , giving cb = da and so ( c, d) "' (a, b). Suppose w e have (a, b) "' ( c, d) and ( c, d) "' (e, f) then ad = be and cf = ed. Then using com­

Step

mutativity and associativity we have

(af)d = a(fd) = a(df) = (ad)f = (bc)f = b(cf ) = b(ed) = (be ) d. Since D is an integral domain and d =I 0 we have af = be and so (a, b) "' (e, f) . We let F be the set of equivalence classes of G under "'· We let (a, b ) denote the equivalence class to which (a, b) belongs. We introduce an addition and multiplication on F and claim that these operations are well-defined. We have to show that if (a, b) = (""{j!Jji) and (c;d) = (C';{F) then

Step

2

(ad + be, bd) = (a' d ' + b ' c', b' d ' )

and

(ac, bd) = (a' c' , b'd ' ) . But

ab' = ba' and cd' = de' and so

(a'd' + b'c') (bd) = (a'd') (bd) + (b'c') (bd) = (a'b) ( dd ') + (c'd) (bb') = (ab') (dd ' ) + (cd ') (bb') = (ad ) (b'd') + (bc) (b'd') = (ad + bc) (b'd')

161

Rings

and

(ac) (b'd') = (ab' ) (cd') = (ba' ) (dc') = (a'c' ) (bd ) . Intuitively

from which

ad + bc a'd' + b'c' . bd b' d'

Also

Hence (ad + bc, bd) "' (a'd' + b'c', b'd' ) and result. Thus our definitions are well-founded.

a

c a' c' . = . . b d b' d'

(ac, bd) "' (a'c', b'd' )

giving the

Step 3 We prove that F is a field. Addition is closed and also associative since

[(a, b) (c, d)] + (e, f ) = (ad + bc, bd) + (e;]) = (adf + bcf + bde, bdf) = (a, b) + (cf + de, df ) =

(a, b) + [(c, d) (e, ! )] .

The identity element is (1,1) = (x, x) for all x E D, x :/; 0. We have to show that if (a, b) # (0, 1 ) then (a, b) has an inverse. Since (a, b) :/; (Q,T) we have a = al # bO = 0 and so (b, a) E D x (D \ {0} ) . Then (a, b) (b, a) = (ab, ab) = (1,1) . Similarly (b, a)(a, b ) = (1,1) . Multiplication is commutative. It may be shown that the distributive laws hold and so F is a field. We may also show that the subset of F consisting of the elements (x,T) (x E ID>) is a sub-integral domain of D and that the mapping

x -+ (x, l ) (x E D) embeds

[Intuitively x T .] --+

D in F.

Defi n ition 7 The field F, constructed in Theorem 9, is called the quotient field of D.

D

Groups, Rings and Fields

162

Remark From Z we construct Q as the quotient field of Z. From the polynomial domain Q [x] we construct Q(x) (note round brackets) as the field of 'rational functions in x' over Q.

Exercises 5.2

1 . In Z7 find the roots of the following polynomials and factorize the polynomials as fully as possible: 2 2 x + 2x + 4, x + x + 3, X 6 - 1 . -

2. In Zr find the inverses of 2, 3 and 6.

3. In z47 find the inverses of 3, 23, 24 and 32. 4. Over Z5 solve, if possible, the following pairs of simultaneous equa­ tions. 2x + 3y = I, (i) 3x + 2y = 4. " " X + Jy = 2, (11) 3x + 2y = 2. 5. Over Z3 1 solve, if possible, the following simultaneous equations. 1 5x + 25y = 1 6, Sx + 21y = 1 8. 6. For the field F, given as Example 9 no. 3 above and consisting of the four elements 0, 1 , a, {3, solve the following simultaneous equations. ax + Y = 1 , X + f3y = {3.

7. Prove that if R is a ring with an identity then the subset invertible elements of R is multiplicatively a group.

U(R)

of

8. Let F be a field and x an indeterminate. What are the invertible elements of F [x] ?

be

the subset { a + b v'3 1 a, b integral domain. Is S a field?

9. Let S

E Z}

of JR. Prove that S is an

163

Rings

1 0. Let S be the subset {a + b v's l a, b E Q} of JR. Prove that S is a field. 1 1 . Let S be the subset { a + b v'6 1 a, b E Q}. Is S a field? 1 2. Let D be an integral domain of prime characteristic p. Prove that, for all a, b E D and n E N , Generalize.

1 3. Let Q

(

)

be the set of 2 x 2 matrices of the form a + ib

c + id -c + id a - ib

(a, b, c, d E IR) .

Prove that Q is a ring which satisfies all the requirements of a field except commutativity of multiplication. (Q is the ring of the quater­ mons, first discovered by W. R. Hamilton, 1805-65 . )

5 .3 Euclidean Domains We have shown that the integral domain of the integers Z and the polynomial domain Q [x] both have division and Euclidean algorithms. Here we study certain integral domains which are assumed to admit a division algorithm from which a Euclidean algorithm is naturally derivable.

Defi nition 8

--+

Let D be an integral domain. Let there exist a mapping

v : D \ {0} with the following two properties.

{0, 1 , 2, . . . }

1 . For all a, b E D \ {O} , v(a) � ( ab) . 2. For all a , b E D \ {0} , there exist q, r E D such that a = bq + r where either r = 0 or, if r =I 0, then v(r) < v(b) . Then D with the mapping v is called a Euclidean domain.

Exa m ples 12 1.

Z

with the mapping v defined by v( a) = I a I (a E Z, a =I 0) is a Euclidean domain. To see this, we observe

Groups, Rings and Fields

164

(i)

2.

that

v(ab) = l ab I = I a l i b i � I a I = v(a) (a, b E Z, a, b ::/; 0) since v( a) � 1 , and that (ii) becomes simply a restatement of the division algorithm for Z. F [x] , where F is any field, with the mapping v defined by v( J (x)) = deg f(x) ( J (x) E F[x] , f(x) ::/; 0) is a Euclidean domain. To see this, we observe first that for

f(x), g(x) E F[x], f(x) ::/; 0, g(x) ::/; 0, v( J (x)g(x)) = deg ( J (x)g(x)) = deg f(x) + deg g(x) � deg f(x) = v( J (x) ) . Again 2, in Definition 9 , is the division algorithm for F[x] . Strictly we have only discussed the division algorithm for polynomial domains over Q or lR but the arguments previously employed for these particular fields easily adapt to any field. We illustrate some of these arguments in the next example.

Exa m ple 13 Consider Z5 [x] . Let a(x) = 3x4 + 2x3 + 2x 2 + x + 3 and b(a) = x 2 + 2. Suppose we want to find q(x), r(x) E Z5 [x] as in the definition of a Euclidean domain. We perform a long division as follows:

x 2 + 2) 3x4 + 2x3 + 2x2 + x + 3 3x 4 + x2 3 2x + x2 + x 2x 3 + 4x

Thus q(x)

- - = -3x2 + 2x + 1 , r(x) = 2x + 1 .

Before considering other Euclidean domains we prove a convenient lemma. unit if and only if it is invertible.

Recall that an element of a ring is a

Rings

165

Lem ma 3 Let D be a Euclidean domain with identity

1,

as

in Definition 8 .

For all a E D \ {0} , v( 1 ) � v(a) . 2. For a E D \ {0} , v(1) = v(a) if and only if a is a unit of D.

1.

P roof =

1 . v(1 ) � v(1a) v(a) (a E D , a -::j; 0) . 2. Suppose a is a unit. Then there exists b E D such that ab = 1 . Then we have v(a) � v(ab) v(1 ) � v(a) and so v(1 ) v(a) . =

=

Conversely suppose v(a) = v(1 ) . There exist q, r E D such that 1 = aq + r , where if r -::j; 0 we have v(r) < v(a) = v(1) which is false and so r = 0. But, then, aq = 1 and a is a unit. D Our next example of a Euclidean domain occ urs as a subintegral domain of the field of complex numbers. We recall that for complex numbers z1 and z2 we have I z1 z2 l = I z1 l l z2 1 , I Z1

+ z2 l

� I z1 I

+

I z2 l ·

Lem m a 4 Let Z [i] denote the set of complex numbers of the form m + ni ( m, n E Z ) . Then Z [i] is an integral domain.

P roof Z [i] is a non-empty subset of the field C. Now for m1 , m2 , n 1 , � E Z

+ n 1 i) + (m 2 + n 2 i) = ( m 1 + m 2 ) + ( n 1 + n2 )i E Z [i] , - (m l + n 1 i) = ( -m d + ( -n ) i E Z [i] , (m 1 + n 1i ) (m2 + n 2i ) = (m 1 m2 - n 1 n2 ) + (m 1 n2 + n 1 m2 )i E Z [i] .

(m 1

i

The remaining axioms for an integral domain are evidently satisfied.

D

Groups, Rings a nd Fields

166

Defin ition 9 A complex number of the form (after K.F. Gauss) .

m + ni (m, n E Z)

is

called a Gaussian integer

Theorem 10 The Gaussian integers Z [i] form a Euclidean domain under the mapping v given by

v(a) = l a l 2 (a E Z[i] , a ;i O) . Proof 1 . We want to prove that

v(a)

�

v(ab) (a, b, E Z[i] \ {0} ) .

We note first that b = b 1 + b2 i where b 1 , b2 E Z and b� + b� � 1 . Hence v(a) l a l 2 � l a l 2 l b l 2 = l ab l 2 = v(ab) .

so

v(b) = I b I =

=

2. Given a, b

E Z[i] \ {0} , we have to find suitable q, r such that a = bq + r. Now is a complex number which must be of the form a + f3i where a, f3 E Q. We now use a fairly obvious property of Q. Since a must lie between two consecutive integers, we may therefore choose that integer m for which a = m + c:, I c: I < � (for example, a = lf lies between 3 and 4 and we choose m = 4, c: = - �-) Similarly we choose n so that /3 = n + 77, 1 77 I < l Let q = m + ni . Then q E Z[i] . Let r = a - bq. Then r E Z[i] . Thus

�

� = a + /3i = (m + c:) + (n + 77)i = (m + n i) + (c: + 77i) = q + (c: + 77i)

and hence

r = a - bq bq + b(c: + 77 i ) - bq = b(c: + 77 i) . If r = 0 the appropriate q, r have been found. If r # 0 then =

v(r) = l b(e + 77 i) l 2 = l b l 2 l e + 77 i l 2 = l b l 2 (c:2 + 772 )

�

�

l b i2

G + �)

= l b l 2 < l b l 2 = v(b). Hence we have established that

Z [i] is a Euclidean domain.

0

Exa m ple 14 r

5 + 6i, b = 2 - 3i. Suppose we have to find suitable q, E Z[i] such that a = bq + r where either r 0 or if r =F 0 then I r I < I b I = V22 + 32 = m. Now a 5 + 6i (5 + 6i) (2 + 3i) -8 + 27i = 8 27 . = - 13 + 13 1 = b 2 - 3i (2 - 3i) (2 + 3i ) 13 Choosing the integers nearest to - fa and � we obtain, respectively, -1 and 2. Let q = -1 + 2i and r = a - bq = (5 + 6i) - (2 - 3i) (-1 + 2i) = (5 + 6i) ­ (4 + 7i ) = 1 - i. We note that l r l = V1 2 + 1 2 = v'2 < m. Thus we have found an appropriate q , r. However, we may also note that q , r are not uniquely determined, for if q ' = 2i and r' = a - bq' = (5 + 6i) - (2 - 3i) (2i) = - 1 + 2i then l r' l = J5 and so q ' and r' also satisfy the required conditions. Let a =

=

Exercises 5. 3

1. 2.

Find the units of the Euclidean domain Z[i] . In the Euclidean domain Z[i] for given that a = bq + r where 0 � l r l < l b l :

a, b E Z[i]

find

q, r E Z[i]

such

a = 1 + 13i, b = 4 - 3i, (ii) a = 5 + 15i, b = 7 + i, (iii) a = 5 + 6i, b = 2 - 3i. 3. Let D = {a + .Bv'21 a, .B E Z}. Prove that D is a Euclidean domain if v : D \ { 0 } -+ {0, 1 , 2, . . . } is given by v(a + ,B-./2) I (a - .Bv'2)(a + ,B-./2) I = I a2 - 2.82 1 (a, .B E Z) . (i)

=

4. (Hard) Let w be a non-trivial complex cube root of 1 . Then w3 = 1 , w =F 1 and so w2 + w + 1 = 0 and the complex conjugate of w is

= w2 = �. (For the considerations of this example it is best to ignore w -1 ± i v'3.) the fact that w 2 Prove that D = {a + ,B w I a, .B E Z } is a Euclidean domain if v : D \ { 0 } -+ {0, 1 , 2, . . . } is given by v(a + ,B w) = I a + ,B w l 2 = (a + ,B w) (a + ,BW) . w

=

168

Groups, Rings and Fields

5.4 Ideals and Homomorphisms

P. Fermat (1601-65) , in commenting on the 'Arithmetica' of Diophantus (c. 250 AD ) , formulated a statement, of which he claimed to have a proof, that the equation, had no solutions for non-zero integers x, y, z. This celebrated assertion, known as Fermat's Last Theorem, has in fact been established as correct owing to the recent work of A. Wiles (1953- ) . In the 19th century, however, its proof was attempted by many mathematicians among whom was E.E. Kummer (1810-93) who tried heroically to establish a complete result. Arising from his efforts he created a theory of 'ideal numbers' but it fell to Dedekind to introduce 'ideals', albeit in a number-theoretic and so commutative context . For our purposes we shall give a general definition of an 'ideal' appropriate to a possibly non-commutative context.

Defin ition 10 Let R be a ring and let I be an additive subgroup of R. 1 . If for all x E R and for all a E I, it follows that xa E I, then I is said to be a left ideal of R. 2. If for all x E R and for all a E I, it follows that ax E I, then I is said to be a right ideal of R. 3. If for all x E R and for all a E I, it follows that xa E I and ax E I, then I is said to be a tw�sided ideal, or briefly, an ideal of R. R and {0} are immediately ideals of R, and {0} is called the zero ideal of R. If I satisfies 1 , 2 or 3 and I ::/; {0} , I ::/; R, then I is said to be proper . By definition every left or right ideal of R is a subring of R but not every sub­ ring of R is necessarily a left or right ideal. Every element of R gives rise to a left or right ideal which may not, however, be proper ( see Theorem 1 1) .

Exa m ples 15 1 . Let n E Z. Then nZ = {nx l x E Z} , the subring of those integers divisible by n, is an ideal of Z. (In a commutative ring every left or right ideal is also a two­ sided ideal. )

169

Rings

2. Let

R be the ring M2 (Q)

of all 2

x

2 matrices over

Q. Let

Then L is easily shown to be an additive subgroup of R and L is also a left ideal since, for x , y, z, t , p, q E Q,

( y) ( ) ( X

z

t

0 p 0 q

=

0 xp + yq (J zp + t q

)E

L.

Lem ma 5 1 . Let R be a ring with an identity 1 and let I be a non-zero left ideal of R. If I contains a unit of R then I = R. 2. A field has no proper left or right ideals.

P roof 1 . Let u be a unit of R such that u E I. Then there exists v E R such that vu = 1 . Let x E R. Then x = x1 = x (va ) = (xv) u E I since I is an ideal. Hence I = R. 2. Every non-zero element of a field is a unit. Hence the result follows. D

Exa m ple 16 We have seen, in the Example above, that M2 (Q) has at least one proper left ideal. We wish to show that M2 ( Q ) has no proper two-sided ideals. Suppose I is a non-zero ideal of M2 (Q) . Let

be a non-zero element of I. Then certainly one of a, b, c, d is non-zero. For the sake of argument we suppose a "I 0. (The reader should consider in turn the cases of non-zero b, c, d and modify the argument to follow.) Since I is an ideal

is an element of I and so also is

Similarly

belong to I. Hence, for

x, y, z, t E Q,

(: :) = (� �) (� �) + (� :) (� �) + G :) G �) + (: �) C �) El

The next theorem, which may be passed over on a first reading, brings together, nevertheless, some useful facts and, at the same time, serves to define some convenient notation.

Theorem 1 1 Let R be a ring. 1 . Let

a E R. Then Ra defined by Ra = {xa l x E R}

is a left ideal of R.

3.

+ + • • •

+ a2 +

+ + . .. +

L 1 , L2 , , Ln be left ideals of R. Then L 1 L2 Ln defined by L 1 L2 + an I ai E Li, i = 1 , 2, . . . , n} + Ln = { a 1 is a left ideal of R. Let a l l � , an E R. Then Ra 1 . . + Ran = { x 1 a 1 Xn an I xi E R, i 1 , 2, . . , n}

2 . Let

.

. .

• • . •

+ R� + .

is a left ideal of R.

.

.

.

+ x2� + ... +

= .

171

Rings

P roof 1. 0 =

2.

Oa E R.a , and for all x 1 1 x 2 , y E R we have x 1 a + x 2 a = (x 1 + x 2 )a E R.a , -(x l a) = ( -x l )a E R.a . Thus Ra is a left ideal. We prove the result for two left ideals A and B. The general result is obtained by a simple induction. A + B = {a + b l a E A, b E B} and A + B is an addi­ tive subgroup of R. Let x E R, a E A, b E B. Then we have x(a + b) = xa + xb E A + B since A, B are left ideals. Thus A + B is a left ideal.

3. This follows from 1 and 2 above.

D

In our considerations of groups we found that normal subgroups of a group and the homomorphisms of a group were important and directly related con­ cepts. A similar relationship will be seen to exist between ideals of a ring and 'homomorphisms' of a ring.

Defin ition 1 1 Let R and S be rings and let

I : R --+ S be a mapping such that l (x + y) = l (x) + l (y), l (xy) = l (x)I(Y) (for all x, y E R) .

Then I is said to be a homomorphism from R to S. The homomorphism 1, as defined above, preserves the additive and multi­ plicative structure of R in its image I(R) in T. Thus I is a homomorphism of R considered as an additive Abelian group and considered as a multiplicative semigroup.

Exa m ples 17

be a given integer, n > 0. Then the mapping I : Z --+ Zn given by l(a) = a where a, the equivalence class to which a belongs (a E Z), is a homomorphism

1 . Let

n

since we know that

2.

a + b = a + b, ab = ab. Let F[x] be a polynomial ring over a field F and let a E F. Then let us define I : F [x] --+ F by I : a(x) --+ a(a) (a(x) E F[x]) .

Groups, Rings and Fields

172

In other words, f replaces a polynomial by the result of substituting a for x in the polynomial. But we know that a(x) + b(x) = c(x), a(x)b(x) = d(x)

(a(x) , b(x ), c(x) , d(x)

E F[x] )

implies that a( a ) + b( a ) = c( a ) , a( a )b( a ) = d( a ) and so f is a homomorphism.

Theorem 12 Let R and S be rings and let f : R --+ S be a homomorphism. Then the following statements hold. 1 . If OR and Os are the zero elements of R and S respectively then f(OR) = Os. 2. For all x E R, - f(x) = f( -x) where -f(x) is the inverse with respect to addition of f( x) in S and -x is the inverse with respect to addition of x in R. 3. f(R) is a subring of S. 4. Let K = {x E R l f(x) = Os} , Os defined in 1 . Then K is an ideal of R.

Proof 1 and 2 hold since f is a homomorphism of R into S where both rings are con­ sidered solely as additive groups. Furthermore, by the same reasoning, f(R) is an additive subgroup of S. To prove that f(R) is indeed a subring of S we have merely to establish multiplicative closure of f(R) in S and this occurs since f is a homomorphism from R to S considered as multiplicative semigroups. Hence, finally, we conclude that f(R) is a subring of S. To prove 4, we observe that K is the kernel of the homomorphism f from the additive group R to the additive group S. Let now a E K, x E R. Then

f(xa) = f(x)f(a) = f(x)Os = Os,

f(ax) = f(a) f(x) = Osf(x) = Os.

Hence xa, ax

E K and so K is an ideal.

D

Defi nition 12 Let R and S be rings and let f : R --+ S be a homomorphism. Then K = {x E R l f(x) = Os} is an ideal of R which is called the kernel of f, written Ker f.

173

Rings

We now come to several definitions and results which correspond to definitions and results previously considered in Chapter 4. As the results and proofs are so similar, those to be provided here will be less detailed than usual. The reader should, however, ensure that he or she fully understands the arguments. We recall that an ideal I of a ring R is, in fact, an additive subgroup of the additive group R and so we have cosets of I in R where the coset containing x E R is

x + I = {x + a i a E I}.

Lemma 6 Let R and S be rings and let f : R --+ S be a homomorphism with kernel K . Let x and y be elements of R. Then f(x) = f(y) if and only if x + K = y + K.

P roof We have shown previously that y + K are equal.

f(x) = f(y) if and only if the cosets x + K and 0

Theorem 13 Let I be an ideal of the ring R. Let R/ I denote the set of cosets of I in R. Two binary operations are defined on R/ I as follows: Let x + I and y + I be cosets of I in R and define

(x + I) + (y + I) = (x + y) + I, (x + I ) (y + I) = xyi. Then the binary operations are well-defined and under these operations R/I is a ring. Further the mapping R --+ R/I given by x --+ x + I (x E R) is a homo­ morphism of R onto R/ I with kernel I.

P roof Certainly under the definition of addition R/ I is an additive group. We have to show that multiplication is well-defined in R/I. Thus we have to show that if x + I = x' + I (x, x' E R) and y + I = y' + I (y, y' E R) then xy + I = x'y' + I. But certainly x + I = x' + I implies that x' = x + a for some a E I, also y' = y + b for some b E I. Then x'y' = (x + a) (y + b) = xy + ay + xb + ab. But I is an ideal and hence we have ay + xb + ab E I. Thus x'y' + I = xy + (ay + xb + ab) + I = xy + I. Our definition of multiplication is well founded.

174

Groups, Rings and Fields

To prove the associativity of multiplication we have for all

x, y, z E R

[(x + I)(y + I)] (z + I ) = (xy + I) (z + I) = (xy)z + I = x(yz ) + I = (x + I) (yz + I) = (x + I) [(y + I) (z + I)] . The distribution laws may be proved and we conclude that R/ I is a ring. The mapping f : R --+ R/I given by f(x) = x + I (x E R) is a homomorphism of the additive group R onto Rj I. For x, y E R we have f(xy) = xy + I = (x + I ) (y + I ) = f(x)f(y) and so f is a ring homomorphism. Finally Ker f = { x E R I J (x) = I } = {x E R i x + I = I } = I. D Definition 13 Let I be an ideal of the ring R. The ring R/I, as considered above, is said to be a

factor-ring of R.

Exa m ple 18 For each n E Z, nZ = { nx I x E Z} is an ideal of Z and the factor-ring ZjnZ is the ring which we have called Zn ·

Defi nition 14 Let R and S b e rings and let f : R --+ S b e a homomorphism. I f f is surjective then f is said to be an epimorphism. If f is injective then f is said to be a mono­ morphism. If f is bijective then f is said to be an isomorphism.

Rema rk In Theorem 8 we had an 'embedding', as it was called, of an integral domain D

into its quotient field F. By an embedding we now understand an isomorphism and we have therefore already shown that there exists an isomorphic copy of D contained in F. In this instance we may identify D with its isomorphic copy and so regard D as a sub-integral domain of F, just as we regard Z as embedded in, and a sub-integral domain of, Q.

Rings

175

Theorem 14 Fi rst Isomorph ism Theorem Let R and S be rings and let Rf K and S are isomorphic.

f

:

R -+

S be an epimorphism with kernel K. Then

P roof

K is an ideal of R and so we have an epimorphism R -+ Rf K. We now define h : R/ K -+ S by h(x + K) = f(x) (x E R) . By the proof of the First Isomorphism Theorem for groups h is a well-defined mapping which is, in fact, an isomorphism between the additive groups R/ K and S. We merely have to show that h preserves multiplication. Let x, y E R, then we have h[(x + K) (y + K)] = h[xy + K] = f(xy) = f(x)f(y) = D h(x + K)h(y + K). The proof is finally complete.

Lem ma 7 Let R be a ring. Let S be a subring of R and let I be an ideal of R. Then S + I = { x + a I x E S, a E I } is a subring of R and I n S is an ideal of S.

P roof We leave this proof to the Exercises.

D

Theorem 15 Second Isomorphism Theorem Let R be a ring. Let S be a subring of R and let I be an ideal of R. Then the factor-rings (S + I)/I and Sj (I n S) are isomorphic.

P roof We define p :

S -+ (S + I)/I by p(x) = x + I (x E S). Then p is an epimorphism. If K is the kernel of p then, by the First Isomorphism Theorem, S/ K is isomorphic to ( S + I)/ I. On proving that K = I n S the proof is complete. D

Groups, Rings and Fields

176 Exercises 5. 4

1 . Prove that

A

=

{ ( � �) lx, Q} t E

2. Let L 1 and L2 be left ideals of a ring ideal of R. Generalize. 3. Let

L1

�

L2

�

is a right ideal of M2 { Q).

R.

Prove that

L 1 n L2 is a left

L3 � . . . be a countable ascending chain of left ideals

of a ring R. Prove that

00

U Li is a left ideal of R.

i=l

X be a non-empty subset of a ring R. Let A = {a E R I xa 0 for all x E X} . Prove that A is a right ideal of R.

4 . Let

=

5. Let R be a ring not necessarily possessing an identity. Let a E R. Prove that { na + xa I n E Z, x E R} is a left ideal of R containing a. 6. Let R and S be rings and let f : R --+ S be a homomorphism. Let L be a left ideal of S. Prove that {x E R l f(x) E L } is a left ideal of R.

7. Let R and S be rings and let f : R --+ S be an epimorphism. Let L be a left ideal of R. Prove that f(L ) is a left ideal of S. 8. Let R be a ring and let S be a subring of R. Let I be an ideal of R. Prove that S + I = { x + a l x E S, a E I } is a subring of R and I n S is an ideal of S. 9. Let R, S and T be rings and let f : R --+ S and g : S --+ T be given homomorphisms. Prove that g o f is a homomorphism from R to T. 10. Let

R be the ring of 2 x 2 matrices of the form a b (a, b E R) . -b a

(

)

Prove that the mapping

( -ba

. --+ a + 1b

is an isomorphism of C with R.

(a, b E R)

177

Rings

5.5 Principal Ideal and Unique Factorization Domains

We here continue our study of integral domains with a view to obtaining proper­ ties very similar to those of the integral domain of the integers z.

Definition 15 Let D be an integral domain. Let a, b E D, b a if there exists c E D such that a = be.

::/; 0. Then b is said to be a divisor of

We recall that u is a unit of a ring R if there exists v

E R such that uv =

vu

= 1.

Defi nition 1 6 Let D be an integral domain. Let a, b exists a unit u in D such that a = bu.

E D.

Then

a is an 8&80Ciate of b if there

Notice that if a is an associate of b then b is an associate of a for if a = bu where uv = vu = 1 then av = buv = b1 = b. An element u is a unit if and only if u is an associate of 1. We further recall that if R is a ring and a E R then Ra = { xa I a E R} and if, in particular, R has an identity 1 then a = 1a E Ra.

Lem ma 8 Let D be Da � Db.

an integral domain. Let

a, b E D.

Then

b

divides

a

if and only if

P roof If b divides a then a = cb for some c E D. Then Da = Deb � Db. Conversely if Da � Db then a E Da � Db and so there exists c E D such that a = cb. D

Lem ma 9 Let D be an integral domain. Let equivalent.

1 . Da = Db. 2 . a divides b and b divides a. 3. a and b are associates. 4. a = bu for some unit u of D.

a, b E D.

The following statements are

178

Groups, Rings and Fields

Proof By Lemma 8, 1 and 2 are equivalent and by remarks above 3 and 4 are equi va­ lent. We prove the equivalence of 2 and 3. If a divides b and b divides a there exist c, d E D such that b = ac, a = bd. Then a = b d = acd from which, as D is an integral domain, 1 = cd and so d and c are units. Hence a and b are associates. On the other hand if a and b are associates there exist units u, v E D such that a = bu and b = av. Hence b divides a and a divides b. This completes the proof. D

Exa m ples 19 1 . Two integers m , n are associates in Z if and only if m = ±n. In Z Lemma 9 is obviously true. 2. Let F be a field. The units of F[x] , the polynomial ring of F over x, are the non-zero elements of F. Therefore f(x) , g(x) E F[x] are associates if and only if f(x) = cg(x) where c E F, c =I 0.

Defi nition 17 Let D be an integral domain. A non-zero element p of D, which is not a unit, is said to be irreducible if whenever a E D and a divides p then a is an associate of 1 or p.

Defi nition 18 Let D be an integral domain. A non-zero element p of D, which is not a unit, is said to be a prime if whenever p divides ab (a, b E D) then p divides a or p divides b. For our convenience we make the following definition for a restricted class of rings; we content ourselves with remarking that, with appropriate modification, the restrictions in the definition may be removed.

Defi n ition 19 Let R be a commutative ring with an identity. 1 . An ideal P of R, P =I R, is said to be prime if whenever a , b E R and ab E P, then either a E P or b E P. 2. An ideal M of R, M =I R, is said to be maximal if whenever M � I and I � R for any ideal I, then either M = I or I = R.

179

Rings

Theorem 16 Let

1.

R be a commutative ring with an identity.

An ideal P of R is prime if and only if Rj P is an integral domain.

2. An ideal M of R is maximal if and only if R/ M is a field.

P roof We note that the factor-ring in identity 1 .

1.

1 and 2 is, at least, a commutative ring with an

P be prime. Let a, b E R be such that (a + P) (b + P) = P. Then we have ab + P = P and so ab E P. AB P is prime a E P or b E P which implies a + P = P or b + P = P. Hence, Rj P has no proper divisors of zero and so Let

is an integral domain. Let now Rj P be an integral domain. Let a, b E R be such that ab E P. Then (a + P ) (b + P) = ab + P = P and so we have divisors of zero in R/P. Since R/ P is an integral domain a + P = P or b + P = P from which a E P or b E P. Hence P is prime. 2 . Let M be maximal. Let a E R be such that a + M ::1 M. Then a ¢ M and so the ideal Ra + M contains a and M and so M C Ra + M. Since M is a maximal ideal Ra + M = R. Then there exist x E R and m E M such that

xa + m = 1 . Hence

1 + M = (xa + m) + M = xa + m + M = xa + M = (x + M)(a + M) . Thus x + M is the inverse of a + M. Hence R/ M is a field. Let now Rj M be a field. Let I be an ideal such that M s; I s; R. If M ::p I there exists a E I, a ¢ M. Then a + M ::1 M and so, as R/ M is a field, a + M is invertible in R/ M and there exists b E R such that (a + M)(b + M) = 1 + M. Therefore ab = 1 + m for some m E M. Hence, as a E I, m E M and M k I we have 1 E I. But then I = R. D

Theorem 17 Let

D be an integral domain. Then a prime is also an irreducible element.

Groups, Rings and Fields

180

Proof Let p be a prime in D. Let a E D and suppose a divides p. We wish to show t hat a is an associate of 1 or p. We have p = ab for some b E D. Since p is prime p divides ab and so either p divides a or p divides b. If p divides a then a = pc for some c E D and so p = ab = pcb and 1 = cb. Thus b is a unit and p and a are associates. On the other hand, if p divides b then b = dp for some d E D and so we have p = ab = adp and 1 = ad. Thus a is an associate of 1. This completes the proof. D In the integral domain Z every irreducible element is also prime. In analogy with Z we wish to investigate those integral domains in which every irreducible element is prime. To facilitate our investigation it is convenient to make a defi­ nition which is obviously modelled on the Fundamental Theorem of Arithmetic in z.

Defi nition 20 Let D be an integral domain in which every non-zero element, which is not a unit , is expressible as a finite product of irreducible elements. Furthermore, whenever a non-zero element x of D which is not a unit , is written as X = P1P2

·

· ·

Pm

= Ql Q2

·

·

·

Qn

where p1 , P2 , . . . , pm ; q1 , q2 , . . . , qn are irreducible elements then m = n and, with a suitable reordering if necessary, Pi and qi are associates ( i = 1 , 2, . . . , n) . Then D is said to be a unique factorization domain (U.F.D.). By the Fundamental Theorem of Arithmetic Z is a U.F.D.

Theorem 18 In a unique factorization domain every irreducible element is prime.

Proof

D be a U.F.D. Let x be an irreducible element of D. Suppose x divides ab (a, b E D) . We have to show that x divides a or x divides b. By supposition there exists y E D such that xy = ab. Let

181

Rings

Now y, a and b are products of irreducible elements, say,

a = P1P2 . Pm , b = q1 q2 qm Y r 1 r2 re , where p1 , P2 , . . . , Pm ; q1 , (J2 , . . . , qn ; r 1 , r2 , . . . , rt are irreducible elements. Then xr 1 r2 Tt = P1P2 Pm q1 q2 qn . But these are two factorizations into irreducible elements and so, as D is a U.F.D . , we must have 1 + t = m + n and, more importantly, every irreducible · ·

· ·

·

·

·

·

·

·

·

=

·

· ·

·

· ·

element on the left-hand side must be an associate of an irreducible element on the right-hand side. Thus x is an associate of some Pi or some qi . But this implies that x divides a or x divides b. D

Defi nition 2 1 Let D be an integral domain. Let a, b, c be non-zero elements of D. Then c is said to be a common divisor of a and b if c divides a and c divides b. A common divisor d, which is itself divisible by any other common divisor, is called a greatest common divisor ( G .C.D. ) . The terminology of this definition corresponds to the terminology of Defini­ itions 3 and 4 of Chapter 2 in the case of the integers. As in that case, we may show that in a U.F.D . any two non-zero elements have a G.C.D. We defer the discussion of a G.C.D. until after we have discussed 'principal ideal rings'.

Definition 22 Let D be an integral domain. Let a E D. Then Da { xa I x E D } is said to be a principal ideal. An integral domain in which every ideal is principal is called a principal ideal domain (P.I.D. ) . =

Lem ma 10 Let D be a principal ideal domain. Any two non-zero elements a and b of D have a G. C.D. d given by

Da + Db = Dd. P roof

Da and Db are ideals of D and so Da + Db is also an ideal. Hence as D is a P.I.D . there exists d E D such that Da + Db = Dd. We claim that d is indeed a G.C.D. of a and b. Certainly Da � Dd and so d divides a and similarly d divides b. Thus

Groups, Rings and Fields

182

d is a common divisor of a and b. Suppose c E D is also a common divisor of a and b. Now d E Da + Db and so there exist x, y E D such that d = xa + yb . But now if c divides a and c divides b we must have that c divides d. Thus d is a G.C.D. of a and b. D We now relate our earlier discussion of Euclidean domains to principal ideal domains.

Theorem 19 A Euclidean domain is a principal ideal domain.

P roof Let D be a Euclidean domain with mapping v : D \ {0} --+ { 0, 1 , 2, }. Let I be an ideal of D. We wish to prove that I is a principal ideal. H I = { 0} the result is true so suppose I ::F {0}. Choose an element b of I for which, amongst all the non-zero elements of I, v(b) is as small as possible. As I is an ideal Db � I. We shall show that Db = I. Let a E I. As D is a Euclidean domain there exist q, r E D such that

a = bq + r where either r 0 or, if r ::F 0, then v(r) < v(b). But, as I is an ideal, r = a - bq E I. But if r ::F 0 we have v(r) < v(b) and this contradicts the choice of b as being such that v(b) is as small as possible. Thus r 0 and a = bq E Db. Hence, finally, lli = L D =

=

Exa m ples 20

1 . Z is a Euclidean domain and we now know that every ideal of Z is of the form nZ = {nx l x E Z} for some n. 2. The polynomial ring F[x] , where F is a field, is a Euclidean domain and so is a P.I.D .

Theorem 20 In a principal ideal domain every irreducible element is prime.

183

Rings

P roof

D be a P.I.D . Let p be an irreducible element of D. Let p divide ab where a, b E D. We wish to show that p divides a or p divides b. Suppose p does not divide a. Let c E D be such that c divides p and c divides a.

Let

Since p is irreducible c is a unit or an associate of p. If c is an associate of p then as c divides a so also does p divide a which is false. Hence c is a unit. Hence, by Lemma 10,

Da + Dp = Dd where d is necessarily a unit and so Dd = D, giving Da + Dp = D. Hence there exist x, y E D such that xa + YP = 1. But then

xab + ypb = b from which p divides

b. Hence p is a prime.

0

Corollary

D be a principal ideal domain. Let p be an irreducible element of D. a 1 , � , , an E D and suppose p divides a 1 � an . Then for some i (1 � i � n) , p divides ai.

Let Let

•

.

•

.

.

.

Proof Either p divides result.

a1

or p divides

a 2 a3 . . . an .

A simple induction proves the 0

Our aim is to prove that a P.I.D . is necessarily a U.F.D. We are thereby enabled to deduce that a Euclidean domain is a U.F.D . At a first reading the reader may wish to confine himself or herself to the fact of the deduction and to avoid the necess ary proofs. We have a lengthy lemma before the main theorem.

Lem ma 1 1 Let D be a principal ideal domain. Let a be a non-zero element of D which is not a unit of D. Then a is the product of a finite number of irreducible elements.

Groups, Rings and Fields

184

Proof We argue by contradiction. Suppose therefore that a is not the finite product of irreducible elements. Since a cann ot itself be irreducible, a is divisible by a 1 , say, a 1 E D, where a 1 is neither a unit nor an associate of a. Hence there exists b1 E D which is also neither a unit nor an associate of a, such that

a = a 1 b1 . But this implies that and since a 1 is not an associate of a we have

Da C Da 1 . Now either a 1 or b1 is not a finite product of irreducible elements. Suppose a 1 is not a product of irreducible elements. We apply the same argument to a 1 which is not a product of irreducible elements and we obtain a 2 dividing a 1 where

Da 1

C

Da 2

and where a2 is not a product ofirreducible elements. We continue this process to obtain a strictly ascending chain of ideals Dan (n E N) such that

Da c Da 1 where each an

c

D� c . . .

(n E N) is not a product of irreducible elements. Let I=

00

U

n= l

Dan ·

Then I is an ideal of D ( see Exercises 5 .4, no. 3) and so I = De for some e E D. But e must belong to some subset of the infinite union and so there must exist k such that e E Dek. But then

I = De � Dak � I and so I = Dak. But this implies that Dak = Dak + 1 = . . .

and this contradicts the fact that the ideals in the chain are distinct. Hence our orig inal supposition is false and a is indeed a finite product of irreducible elements. D

Theorem 2 1 A principal ideal domain is also a unique factorization domain.

185

Rings

P roof Let D be a P .I.D . By Lemma 1 1 we have shown that every non-zero element of D which is not a unit is a finite product of irreducible elements. We have to show that such a product is essentially unique. Let a E D and let a be expressed as a = P1P2

· · ·

Pm

=

ql q2

·

·

·

qn

where p1 , p2 , . . . , Pm i q1 , q2 , . . . , qn are irreducible elements of D. Then p1 divides q1 q2 . . . qn and so, by the Corollary above, p1 divides one of q1 , q2 , . . . , qn . By renumbering, if necessary, we may suppose p1 divides q1 . Then p1 and q1 are irreducible elements which are associates and so q1 = up1 where u is a unit of D. Then

which implies that P2P3

· · ·

Pm = uq2 q3

· ·

·

qn

=

q I2 q3

·

·

·

qn

where q� = uq2 is an irreducible element. A simple induction now proves the desired result. D

Corol l a ry A Euclidean domain i s also a unique factorization domain.

Exercises 5. 5

1.

Let R be a commutative ring with an identity. Prove that a maximal ideal of R is a prime ideal. Give an example of a ring R and a prime ideal of R which is not maximal in R.

2. Z [i] is the ring of Gaussian integers. Find the G . C.D. d in Z [i] of 4 + 2i and 1 -3i and write d in the form (4 + 2 i ) z1 + (1 - 3 i ) z2 = d

for appropriate z1 , z2

E Z [i] .

3. Let D be a principal ideal domain. Prove that any n non-zero elements a 1 , a2 , . . . , an of D have a G.C.D. d given by Da 1 + Da 2 + . . . + Dan = Dd.

Groups, Rings and Fields

186

5.6 Factorization in

Q[x]

Given a non-zero polynomial f(x) E Q[x] we want to devise a criterion by which the polynomial is a prime, or is equivalently irreducible, in Q[x] . We remark first that any such polynomial f(x) may be written as

f(x) where g(x)

=

1

-

c

g(x)

E Z[x] and c E Z.

Exa m ple 21

It suffices therefore to consider polynomials which are in Z[x] but to attempt their factorization in Q[x] . We aim to show that if a polynomial in Z[x] factors non-trivially in Q[x] then it already has a non-trivial factorization in Z[x] . From this fact we infer that if a polynomial in Z[x] does not factor non-trivially in Z[x] then it does not factor non-trivially in Q[x].

Defi n ition 23 Let f(x) be a polynomial in Z [x] . Then the greatest common divisor of the coefficients of f(x) is called the content of f(x). A polynomial of content 1 is said to be primitive. Let f(x) E Q[x], f(x) ::/; 0. Then we may write d

f(x) = c h(x) -

where

c,

d are integers,

h(x) E Z[x]

and h(x) has content 1 .

We illustrate this assertion by means o f Examples.

Exa m ples 22 1.

14 28 21 1 f(x) = 5 x 2 + 3 x + 2 = 2 . 3 . 5 [84x 2 + 280x + 3 1 5 ] =

7 7 2 30 [ 12x + 40x + 45] = 30 h(x) ,

where h(x) has content

1. 1 1 x +· 1 2. f(x) = 5 xa + g1 x 2 + 6 14 12 1 3 21x2 + 308x + 12] = 8.J. 7 [70x + 1 h(x), = 168 where h(x) has content 1. Lem ma 12

f(x) and g(x) be primitive polynomials in Z[x] . c 1 , c2 E Z, c1 =F 0, � =F 0, such that cd(x) = �g(x) . f(x) = ±g(x) . Let

Suppose there exist Then c 1 = ±� and

P roof Let f(x) = a0 + a 1 x + . . . + anx n (an =F 0) . Then the G.C.D . of a0 , a 1 , . . . , an is and so there exist t0, t 1 , . . . , tn E Z such that

t0 a0 + t 1 a 1 + . . . + tn an = 1. Since cd (x) = �g(x) , c2 divides c1 ao , c 1 a 1 , . . . , cl an and so c2 divides toc1 ao + t 1 c 1 a 1 + + tn cnan = cl (to ao + t 1 a 1 + + tn an ) = c1 . Similarly c 1 divides � · Thus c 1 = ±� and so f(x) = ±g(x) . · · ·

1

· · ·

D

The next lemma holds the key to the use of primitive polynomials.

Lem ma 13 Gauss's Lem ma Let

f(x) and g(x) be primitive polynomials in Z[x]. Then f(x)g(x) is primitive.

P roof

f(x) = ao + a 1 x + . . . + am xm ( am =I 0), g(x) = bo + b1 x + + bn xn (bn =F 0), f(x)g(x) = h(x) = Co + C1 X + . . . + Cm+ n xm + n (Cm + n =f; 0) . If h(x) is not primitive there exists a prime p E Z such that p divides each of eo , e ll . . . , Cm +n· Now p cannot divide all of the coefficients of f(x) or all of the Let

· .

·

Groups, Rings and Fields

188

coefficients of g(x) since f(x) and g(x) are primitive. Suppose therefore that p divides a0, a1 1 , 0-r _ 1 but p does not divide ar where 0 � r < m and that p divides bo, b1 1 , bs _ 1 but p does not divide bs where 0 � s < n. Consider Cr + s· We have • • •

•

•

•

Cr+s = ao br + s + a 1 br + s - 1 + . . . + ar - 1 bs+ 1 + ar bs + ar + 1 bs - 1 + . . . + ar +s bo· Now p divides Cr+s i ao , a 1 , ar _ 1 ; bo , b1 , . . . , bs _ 1 and hence it follows that p divides ar bs and so divides ar or bs . But this is a contradiction and so f(x)g(x) is primitive. D Exa m ple 23

2x 2 + 3x + 1, x 2 + 2 are primitive and so is (2x2 + 3x + 1)(x 2 + 2) = 2x4 + 3x3 + 5x 2 + 6x + 2. We use Lemma 13 to show that if factorization does not occur in Z[x] then it does not occur in Q[x].

Lem ma 14 Let f(x) E Z[x] and let f(x ) have degree n, n > 0. Suppose that f(x) does not factorize in Z[x] into the product of two polynomials of degrees r and s where 0 < r < n, 0 < s < n ( r + s = n ) . Then f(x) does not factorize in Q [x] into the product of two polynomials of degrees r and s.

P roof We argue by contradiction and suppose

f(x)

= g(x)h(x)

where g(x) and h(x) are polynomials in Q[x] of degrees r and s respectively. Now

f(x) = eofo (x), g(x) = C1 9o (x) , h(x) = � ho(x) , d1 d2 where fo (x), 9o (x) and ho (x) are primitive polynomials in Z[x] and eo, c1 1 c2 , d1 1 d2 are in Z. Then eo fo (x) = dC1 9o (x) d� ho (x) 1 2 and

so

Now, by Gauss's Lemma , g0(x)h0 (x) is primitive and so, by Lemma 12, eod1 � = ±c1 c2 and fo (x) = ±go (x)ho (x) . But g0 (x) and ho(x) have degrees r and s respectively and so we have derived a contradiction since f(x) = eo fo (x) = ±g0 (x)h0(x) . Thus the lemma is proved. D We now obtain our main result which is named after F.G.M. Eisenstein

(1823- 52) .

Theorem 22 Eisenstei n 's Criterion Let f(x) E Z[x] and let f(x) exists a prime p such that:

= ao + a 1 x + . . . + anxn (� =I 0) .

Suppose there

p divides a0 , a 1 , . . . , an- 1 1 p does not divide an and p2 does not divide ao . Then f(x) is irreducible as a polynomial in Q[x] . 1. 2. 3.

P roof We argue by contradiction. If f(x) is not irreducible in Q[x] then f(x) is not prime in Q[x] and so f(x) may be factorized in Q[x] into two polynomials of degrees r and s where 0 < r < n , 0 < s < n , r + s = n. There is necessarily a corresponding factorization of f(x) in Z[x] . Hence we may suppose that

f(x) = g(x)h(x) where g(x) and h(x) are polynomials in Z[x] of degrees r and s respectively. Let g(x) = bo + b1 x + . . . + br xr (br =I 0) , h(x) = Co + C1 X + . . . + C8X8 (c8 =I 0). Now a0 = b0eo and since p divides a0 but p2 does not divide a0 , either bo or eo , but not both bo and eo , is divisible by p. Suppose p divides bo but p does not divide Co · If p were to divide b0, b 1 , . . . , br then all the coefficients of f(x) would also be divisible by p and that is false. We suppose therefore that p divides b0 , b 1 , . . . , bk 1 but p does not divide bk for some k where 0 < k :$ r < n. Since ak = bkCo + bk- 1 c1 + . . · + bo ck we have that p divides ak; bo , b1 , . . . , bk 1 and so p divides bkCo. But p does not divide Co and so p divides bk which is false. Hence our initial assumption was wrong and consequently f(x) is irreducible in Q [x] . D _

_

We give some examples of the use of Eisenstein's Criterion.

Groups, Rings and Fields

190

Exam ples 24 1. Let p be a prime. Then xn - p E Q[x] is irreducible by the criterion. 2. 21 6x 2 9x3 4x4 is irreducible in Q[x] on applying the criterion with

+ + +

3.

p = 3.

+ + +...+

71' - 1 is irreducible where p We may also prove that f(x) = 1 x x 2 is a prime. We cannot apply the criterion directly but we may transform f(x) into a polynomial to which the criterion may be applied. Introduce a new indeterminate y where x = 1 + y. Then, temporarily using the quotient field Q(x) = Q(y) of Q[x] , we have 1 /(1 + y) = f(x) = 1 x x 2 + . . . + xP -

+ +

= xP - 1 =

x-1 (1 + y)P - 1 y

[ + ( �) ( � ) � . . . + ( : ) ] 1

=

= Now,

y+

yP - 1

+

y

(�) Y + ( � ) y2 + . . . + ( : ) yP.

we have seen in the proof of Theorem

8,

all of the coefficients in

+ y) are divisible by p except for ( :) 1 , also ( �) = p and so is not divisible by p2 • Thus /( 1 + Y ) is irreducible and so, evidently, is f(x) . as

/(1

=

Exercises 5. 6

+ + + + + +

+ + + +

+

1 . Prove that the following polynomials are irreducible in Q[x] . 5 25x 10x 2 7x3 , 14 21x 49x 2 6x3 , 26 39x 65x 2 10x3 . 2. Prove that 19 + 24x 9x 2 x 3 is irreducible in Q[x] . (Hint: put X = y - 1 .) 3. Prove that x3 + 9 is irreducible in Q[x] .

6 Topics in Group Theory

In this final chapter we extend our knowledge of group theory. Among other aspects of finite groups, we investigate permutation groups and obtain two results of cardinal importance in the theory of finite groups. In the first of these, we establish the structure of Abelian groups and, in the second, we estab­ lish the existence of the so-called 'Sylow p-subgroups' of a finite group.

6 . 1 Permutation Groups We are here concerned with bijective mappings of a non-empty set into itself. Such mappings may be multiplied under the circle-composition of mappings. From our earlier work we easily obtain the following theorem.

Theorem 1 Let X be a non-empty set and let S(X) be the set of bijective mappings of X onto X. Under the circle-composition of mappings S(X) is a group.

Proof From the Examples in Section 4. 1 (Semigroups) , we know that S(X ) is a monoid. Let f E S(X). Then the inverse f - 1 of f is given as follows. f - 1 is that mapping 191

G roups, Rings and Fields

192

for which f - 1 (a) S(X) is a group. Our interest

= b if and only if f(b) = a (a, b E X) . It is then immediate that D

in this section concerns bijective mappings on finite sets.

Defi n itio n 1 A bijective mapping of a non-empty set X onto itself is called a permutation. Any set of permutations of X forming a group is called a permutation group. The permutation group of all permutations on X is called the symmetric group on X and is frequently denoted by S(X) . If X consists of the n symbols or elements x 1 , x 2 , . . . , xn and more particularly if X = {1, 2, . . . , n} then the symmetric group on X is designated as Sn· A permutation p E Sn is written as

p=

( i1

i2

in

)

· · · in where the notation means that p(i 1 ) = i1 , p(i 2 ) = i2 , , p(in ) = in· but not invariably, i 1 , i 2 , . . . , i n are in the natural order 1, 2, . . . , n.) i1

i2

.

•

.

(Usually

Exa m ple 1 The permutation p such that represented by any of

p(1) = 2, p(2) = 1, p(3) = 4, p(4) = 3

)(

(1

)(

2 3 4 4 2 1 3 2 1 4 3 ' ' 2 1 4 3 1 2 3 4 3 1 2 4

may be

)

Defi n ition 2 A permutation p E Sn is said to fix i E {1, 2, . . . , n} if p(i) = i and to move i E {1, 2, . . . , n} if p(i) =I i . The identity permutation, which is the identity of the group Sn , is that permutation fixing all i E { 1 , 2, . . . , n} .

Lem ma 1

Sn is a group of order n(n - 1) . . . 2. 1 = n ! Proof Let p =

(�

J1

2

n

i2

· · · in

).

193

Topics in Group Theory

For }I we have n choices of symbols from {1, 2, . . . , n} . For h we have n - 1 choices of symbols from {1, 2, . . . , n } \ {}I }. For }a we have n - 2 choices of sym­ bols from {1, 2, . . . , n } \ {}I , ]2 } . Continuing we have only one choice for Jn · The total number of choices is n ( n - 1) (n - 2) . . . 1 giving the result. D

Exa m ple 2 Let X = { 1, 2, 3}. Then the symmetric group S3 has order 3! the six permutations,

= 6 and consists of

( : � :) , is the identity permutation. ( � � �) is the permutation p = 2, p(2) = 3 and p(3) = 1. 1 2 3 If q = , then the product pq is obtained from the composition of 3 1 2 the mappings p and q, namely by applying q and then p as follows: such that p(1)

(

)

1 ___!_. 3 -�-d 2 __!.. 1 � 2 3 __!.. 2 � 3 which we also write

(�

as

�) (�

2 3

2 1

� ) = (�

1 2

�) (�

2 1

( Jl�

2

�) = ( :

2

2

:) .

Convention Let

p= Then

p=

( p;1)

( t�l

2 i2 . . .

�).

tn

�)

q=

(;

h

...

:).

�)

2 2 q= p(2) . . . p ) ' q 1) q( 2) . . . q )

Groups, Rings and Fields

194

and the product pq is given by

( t ; � ) ( t ; �J = ( : \ ! �\ ! (���)) ( : � ) =( � � (pq�(n)) . p 1) p 2 ) . . . p ) 1 2 q 1) ( 2 )

q 1) q 2)

q

1 q( 1) q ( ) . . . q )

(pq (1) (pq ( 2)

(The reader is advised that another convention for the multiplication o f permutations is also to be found in some textbooks. ) We give further examples exhibiting our convention for the multiplication of permutations.

Exa m ples 3

1.

(:

2.

(�

:)(�

2 3 4 5 2 4

2 3 4 2 1 3

: ) (: 52 11 32 : ) ( � (: 52 31 42 : ) =

=

2 3 4 5 6 3 7 1 2 4 2 3 2 3

= (: = (�

Lem ma 2 Let p =

( '1�

2 i2

...

�) ( �

2 2 6 4 5 4

n)

. Then p- 1

tn

)

;) (�

3 7 4 7

.

.

3 4 5 6 7 7 3 6 1 4 1 2 3 4 5 6 2 7 3 6 1 6 6 6

7 5 3 5

:) .

= cl1

2 3 4 2 1 3

i2

2

�).

:)

:)

Topics in Group Theory

195

P roof D

Defi nition 3 A permutation p of { 1 , 2, . . . , n } is called a cycle of length r ( 1 < r � n ) if for some subset {i 1 , i 2 , , in } from {1, 2, . . . , n } we have p(i1 ) i 2 , p(i 2 ) = ia , . . . p(ir - d = ir , P (ir ) = i 1 and for j E {1, 2, . . . , n } \ {i l , i 2 , . . . , i r }, p(j) = j. To indicate that the cycle p permutes the integers i 1 , i 2 , , i r cyclically and that the remaining integers are fixed by p we write p, in an abbreviated notation, as •

•

=

.

. • •

p = (i 1 i 2 · · · ir) · A cycle of length 2 is often called a transposition. Conventionally the identity permutation is regarded as a cycle of length 1 and is written as (1).

Exa m ple 4

:)

2 3 4 5 6 7 is the cycle (1 6 2 3 5) , which may also 3 5 4 1 2 7 be written as (6 2 3 5 1) , (2 3 5 1 6 ) , (3 5 1 6 2 ) or (5 1 6 2 3). We note that in cycle notation we write down only the symbols from 1, 2, . . . , n

(�

which are moved. Consequently only the context enables us to determine

whether the cycle ( 1

(1

2 3 4 5 6 6 3 5 4 1 2

6 2 3 5) represents

(1

2 3 4 5 6 7 8 6 3 5 4 1 2 7 8

) etc. Fortunately ambiguity does not usually arise.

) or ,

Permutations expressed in cycle notation are easy to multiply. We illustrate their multiplication in the following example.

Exa m ple 5 Suppose we wish to prove that in S6 we have

(1

3 4 5 2) (6 2 3 4) (1 3 5)

=

(1

5 3 2 4 6) .

Groups, Rings and Fields

196

Letting r = (1 3 4 5 produc t r st,

2) , s = (6 2 3 4) , t = (1 3 5) we have, for the 1 �3�4 �5 2�2�3 �4 3�5�5�2 4�4�6 �6 5�1�1�3 6�6�2�1

and so rst

=

(1

3 4 5 2) (6 2 3 4)(1 3 5)

=

(1

5 3

2 4 6) .

Exam ple 6 The cycles ( 1 7 integers, { 1 , 2, 4,

8 2 4) and (3 7, 8} and {3, 5 ,

6 5) permute cyclically the disjoint sets of 6}. The cycles are easily seen to commute.

Defi n ition 4 Two permutations from Sn are said to be disjoint if the two subsets of integers moved by the permutations are disjoint.

Lem ma 3 Disjoint permutations commute.

P roof Let p and q be disjoint permutations from Sn · Then we know that we have three subsets A, B, C, of which C may be empty, such that { 1 , 2, . . . , n}

=

Au BUG

is a disjoint union and such that p permutes the integers of A among themselves but fixes the integers of B U C and q permutes the integers of B among them­ selves but fixes the integers of A U C. Let a E A, b E B, c E C. Then =

p(a) = q(p(a) )

(pq) (a)

=

p(q(a) )

(pq ) (b )

=

p(q( b ) ) = q ( b )

(pq ) (c )

=

p( q(c) ) = p(c )

Thus pq = qp .

= =

q(p( b) )

( qp ) (a) ,

= =

c = q(c)

( qp ) ( b ) ,

=

q (p(c) )

=

( qp ) ( c) . D

Topics in Group Theory

Exa m ple 7

197

(1

9

g)

2 3 4 5 6 7 8 8 3 6 5 7 4 1 2

is a product of the disjoint, and so commuting, cycles

( 4 6 7) .

(1

9

2 8)

and

We obtain easily the following result.

Theorem 2 Every permutation is a product of disjoint cycles. We have broken down any given permutation into disjoint cycles. We may now break down each cycle into transpositions.

Theorem 3 Every permutation is a product of transpositions.

P roof It is enough to show that every cycle is a product of transpositions. Trivially ( 1 ) = ( 12) (12) . Let now (i 1 , i 2 , . . . , i r) be a cycle of length Then, by direct calculation,

r, r

>

1. D

Exa m ple 8

(1

2 3 4 5 6 7 8 7 1 2 3 4 8 5 6

)

=

(1 7 5 4 3 2) (6 8)

(1 2)(1 3) (1 4) (1 5)(1 7) (6 8) = (5 7) (5 1 ) (6 8) (5 2) (1 2) (3 4) (5 3) (1 2) =

We may express a permutation as a product of transpositions in many, indeed too many, ways but whether an even number or an odd number of transpositions is involved in any particular way turns out to be solely determined by the permu­ tation. In order to prove this mysterious fact we make a digression into rings of polynomials of several commuting indeterminates and we define the 'action' of a permutation upon such polynomials.

Groups, Rings and Fields

198

Defi n ition 5

Z[x 1 , x2 , . . . , Xn] be the polynomial ring of n commuting indeterminates . x Xt 2 , . . . , xn over Z. Let p E Sn and let f(x 1 , x2 , . . . , xn ) E Z[x 1 , x2 , . . . , xn ] · The action of p on f(x 1 , x 2 , . . . , xn ) is then defined to be the polynomial (pf) (x t , x2 , . . . , Xn ) given by (pf) (xt , x 2 , · · · , Xn ) = f(xp( l ) • Xp(2) • . · . , Xp(n) ) · Let

Exam ple 9

f(x 1 , x2 , xa) = xix� + 5x� + 4x�xg E Z [x t , x 2 , xa] . 1 2 3 Let p = E S3 . Then 3 1 2 (pj ) (x 1 , x 2 , x3) = xh� + 5xi + 4xix�. If, in particular, we act upon f(x 1 , x 2 , . . . , xn) E Z[x 1 , x 2 , . . . , xn] , as above, by

(

Let

)

a transposition (ij) (i ::/: j), say, then in effect we interchange the indeterminates xi and xi in the expression for f(x t . x 2 , . . . , xn ) ·

Example 10

(1 2) act on various polynomials. (x� + x� + xa) = x� + xi + x 3 , (x 1 - x 2 ) = x 2 - Xt = - (x t - x 2 ) , (x3 - x 4 ) = xa - x 4 , (x1 - x 2 ) (x 1 - x3 ) (x 2 - x3 ) = (x2 - x1 ) (x 2 - xa) (x l - x3 ) = -(xt - x 2 ) (x 1 - x ) (x 2 - x ) . 3 3

We let the transposition

(1 (1 (1 (1

2) 2) 2) 2)

Defi n ition 6 Let Z[x 1 , x 2 , . . . , xn ] be the polynomial ring of n commuting indeterminates over Z. Let f(x 1 , x 2 , . . . , xn ) be a polynomial from Z[x 1 , x2 , . . . , xnl · If for all trans­ positions t E Sn

(tf)(x t . x 2 , . . . , Xn ) = f(x t . x 2 , . . . , Xn) then f(x 1 , x 2 , , Xn ) i s said to be symmetric. I f for all transpositions t E Sn (tf) (x 1 , x 2 , · · · • xn) -f(x t , x 2 , . . . , xn ) then f(x 1 , x 2 , . . . , xn ) is said to be skew-symmetric. •

•

•

=

A polynomial may be neither symmetric nor skew-symmetric.

199

Topics in Group Theory

Exa m ple 1 1 In Z[x 1 , x2 , x3 ] , x 1 + x2 + x 3 , x� + x� + x�, x 1 x2 + x 1 xa + x2xa and x 1 x2x3 are typical symmetric polynomials. (x 1 - x 2 ) (x 1 - x3) (x2 - x3 ) is a skew-symmetric polynomial. x 1 - x 2 + x3 is neither symmetric nor skew-symmetric. We recall that

denotes the product a 1 a2 . . . an . Let w(x 1 , x 2 , . . . , xn ) be the particular poly­ nomial from Z[x 1 , x 2 , . . . , xn ] given by

w(x l , x 2 , · · · • x n ) =

n

II r

(xr - X8) ,sr <=sl = (x l - x 2 ) (x 1 - x3) . . . (x l - Xn ) (x 2 - x3) . . . (x 2 - Xn ) X

X

Exa m ple 12

Lem ma 4 For all transpositions t from

Sn (tw) (x 1 , x 2 , . . . , Xn ) = -w(x 1 , x 2 , . . . , Xn ) ·

Proof Let t be the transposition (ij) , i < j. t acts on the factors of the product

n

II

rr1s= l <s

(xr - X8) .

A factor of the form xr - x8 where neither r nor s is equal to either i or j is unaltered by t. Factors of the form Xr - x; and Xr - xi where r is not equal to either i or j are simply interchanged by t. Similarly factors x ; - Xr and xi - xr , ( r =I i, j) are interchanged by t.

Groups, Rings and Fields

200

Factors of the form Xr - x; and xi For such a pair of factors we have

- Xr (r =F i,j) must be considered together.

(ij) [(x r - x;) (xj - Xr ) J = (xr - Xj ) (x ; - Xr) = (xj - X r) (x r - X ;) and so the product of the pair of factors is unaltered. The single remaining factor to be considered is X; - xi and for this factor

(ij) (x; - Xj ) = Xj - X ; = -(x; - Xj) and so we have a change of sign. Altogether there is, in consequence, effectively one change of sign and hence we obtain the desired result. D

Corollary

Sn . Then ( pw)(xt . x 2 , . . . , X n ) = ±w(x t. x2 , . . . , xn) ·

Let p be a permutation from

P roof p is a product of transpositions, say p = t 1 t2 • . . tm where t 1 , t 2 , . . . , tm are trans­ positions. Then

( pw) (x l , x 2 , . . . , X n) = (t 1 t2 . . . tmw) (xl , x 2 , . . . , Xn ) = -(tl . . . tm - l w) (x l , x 2 , . . . , X n ) D

Defi nition 7

Sn is said to be even if ( pw)(x t . x 2 , . . . , X n ) = w(x b x2 , . . . , xn)

A permutation p from

and to be odd if

By Lemma 4, a transposition is an odd permutation. From the proof of the Corollary above we obtain the next theorem.

201

Topics in Group Theory

Theorem 4 Every permutation is either even or odd. An even permutation is only expressible as a product of an even number of transpositions. An odd permutation is only expressible as a product of an odd number of permutations. We may go further

as

follows.

Theorem 5 Let An be the set of even permutations from Sn . Then An is a normal subgroup of sn of index 2, I An I � n! =

Proof

A n is obviously closed under multiplication and if p E An then p is a product of an even number of transpositions and so also is p- 1 . Thus An is a group. We claim that Sn = An U An (1 2) . Let p E Sn· If p is even then p E An . If p is odd then p(1 2) is even and so p(1 2) E An from which p E An (1 2) . Therefore Sn � An U An (1 2) giving the result. D Defi n ition 8 The group of the even permutations from { 1 , 2, . . . , n} and is denoted by A n .

Sn is called the alternating group on

Exa m ple 13

A3 = {(1) , (1 2 3), (1 3 2)} . A situation which commonly arises, and which we have encountered, is that in which a group G 'acts' as a permutation group on a non-empty set X. We some­ times say that G 'induces' a permutation group on X. We require to make this terminology more precise.

Defi nition 9 Let G be a group and let X be a non-empty set . Let S(X ) be the group of permutations of X and let f : G ----+ S(X ) be a homomorphism. Then for each a E G, f(a) is a permutation of X and G is then said to act as a permutation

Groups, Rings and Fields

202

group on X or to induce a permutation group on X. As a short notation for the action of G on X we write

a.x = l(a)x (x E X, a E G) . We note that, in this notation,

(ab) .x = l (ab)x = (f(a) l (b))x = l( a) (f(b)x) = a.(b.x) (x E X, a, b E G ) . Furthermore

{a E G I a.x = x for all x E X} and s o G/Ker I i s isomorphic t o a subgroup of S(X) . Ker I =

Defi nition 10 Let G act as a permutation group on a non-empty set X. Let x E X. Then the orbit containing x is defined to be G(x) = {a.x l a E G} . The stabilizer of x is defined to be Stabc (x)

= {a E G l a.x = x}.

Theorem 6 Let G act as a permutation group on a non-empty set X. A relation "' is defined on X by x "' y (x, y E X) if and only if a.x = y for some a E G. 1 . Then "' is an equivalence relation and each equivalence class is an orbit. 2 . If X is finite the number of distinct elements in the orbit of x E X is given by I G : Stabc (x) I·

P roof 1 . Certainly for all x E G, e.x = x and so x "' x. If x "' y (x, y E X) then there exists a E G such that a.x = y. Hence it follows that x = e.x = (a - 1 a) .x = a- 1 . (a.x) = a -1 .y and so y "' x. If x "' y and y "' z (x, y, z E G ) then there exist a, b E G such that a.x = y and b.y = z, from which (ba) .x = b.(a.x) b.y = z and so x "' z. 2. G(x) = {a.x l a E G} is the orbit of x. Let =

G = a 1 Stabc (x) U a2 Stabc (x) U . . . U a,.Stabc (x) be a coset decomposition of Stabc (x) in G. Then we claim that the elements a 1 .x , a2 .x, . . . , am.x are distinct and constitute the entire orbit containing x.

The proof is very similar t o that in Chapter 4 , Theorem 19, in which we proved that the number of elements in a conjugacy class of a group is equal

203

Topics in Group Theory

to the index of the centralizer of an element in the class . The group acts as a permutation group on the conjugacy class. The reader should establish for himself or herself the details of the present proof. D We may now prove a result first established by Cayley in

1878.

Theorem 7 Cayley's Theorem

A finite group of order n is isomorphic to a subgroup of the symmetric group Sn.

P roof Let G have distinct elements x 1 , x 2 , . . . , x n. Then G acts as a permutation group on G where G is considered simply as a non-empty set . The action is given by

a . x; = ax1 (a E G, i = 1, 2, . . . , n ) since we have

ab.x; = (ab)x; = a(bx;) = a.(b.x;) (a, b E G, i = 1, 2, . . . , n ) . Furthermore a E G acts as the identity permutation on X if and only if ax; a.x; = x; (i = 1, 2, . . . , n ) which is so if and only if a is the identity of G. Thus G is isomorphic to a subgroup of the symmetric group on {x 1 , x 2 , . . . , xn} · [In fact the isomorphism is given explicitly by x 1 x 2 · . X n .] a D axn ax 1 ax 2 =

�

(

)

·

Exercises 6. 1

1.

2.

Evaluate the following products:

(�

Prove that

(�

2 1 2 1

3 4 3 4

4 2 4 3

5 6 5 6

:) ( � :) ( �

2 4 2 3

3 6 3 4

4 3 4 5

5 2 5 6

) �� . ).

( 1 2 9 3 4) (5 6 2 8 1) (7 8 9 1) = (1 7 2 8 3 4) (5 6 9) . 3.

Write the following cycles

as

products of transpositions:

(1 3 5 7 6 2) , (1 2 4 3) , (6 7 1 2 5 8 4) . Which cycles are even and which are odd?

Groups, Rings and Fields

204

4. Write down the elements of the A4 • 5. Is the polynomial (x 1 - x 2 ) (x 1 - x3) (x2 metric, skew-synunetric or neither?

x3

) (x 1

+

x2

+

x3)

sym­

6. Let G be a group and let f : G -+ S(X ) be a homomorphism of G into the group S(X) of permutations on a finite set X. Prove that Ker f =

7. 8.

n Stabc (x) .

xeX

Write down the full proof of Theorem 6 , part 2. Let X = {H1 , H2 , . . . , Hn } be a complete set of conjugates of a sub­ group H of a group G. Prove that an action of G on X is defined by a.Hi = aHi a- 1 (a E G, i = 1, 2, . . . , n ) . Prove that

n

= I G : Nc (H) I .

9. Find an isomorphism between the S3 and the non-Abelian of order 6, the Cayley table of which is in the Examples 1 1 no. 3 of Section 4.2.

6.2 Generators and Relations When we discussed various finite groups in Chapter 4 we often wrote down their Cayley tables. It was evident that these tables were only useable for groups of order perhaps at most 2 0 and so their use had obvious limitations for describing finite groups in general. We here develop a more efficient means of describing groups, whether finite or infinite.

Exa m ple 14 Let us consider the group G of order 6 given in Examples 11 no. 3 of Section 4.2, in which G = { e, a, b, c, d, !} is the group of mappings of IR \ {0, 1 } into IR \ {0, 1 } for which the Cayley table has been given. We have a3 = e, c2 = e . Suppose we try to find the least subgroup H of G con­ taining a and c. Certainly H contains e, a, a2 , c, d = ac and f = a 2 c and so H = G. Thus we say that a and c 'generate' G. Could we determine the Cayley table from simply 'knowing' a and c? The answer is 'not quite', because a and c are not unrelated since we have ac = ca2 (= d) and a2 c = ca (= f) . But these relations may be rewritten as c- 1 ac = a2 , c- 1 a2 c = a and the second is a . c- 1 a 2 c = ( c -1 ac) 2 = ( a2 ) 2 a4 = a. But now consequence of t he first smce knowing the fact that in G we have a3 = e, c2 = e, c- 1 ac = a 2 we may work =

Topics in Group Theory

205

out the products of elements such as df by using only this fact and by using the legitimate operations of a group; thus we may determine df as follows. We have d = ac and f = a 2c and so df = (ac) (a2 c) = ac - 1 a2 c = aa = b. We can obtain all the entries of the Cayley table in this way. Thus we may derive the Cayley table from knowing that we have a group generated by two elements a and c with the 1 . a3 = e, c2 = e , c- ac = a2 . we wr1"t e re1attons G = ( a, c I a3 = e, c2 = e, c -1 ac = a 2) .

Exam ple 15 Suppose we consider a group G with generators a and c as in the previous example but with a slight modification of the relations, namely we suppose 1 a3 = e, c2 = e, c- ac = a. By virtue of the fact that a and c commute, we may collect together in any product of a's and c 's the powers of a and c. Using the relations above we see that G = { e, a, a 2 , c, ac, a2 c} and is an Abelian group of order 6. We may write down a Cayley table as shown below: e e

e

a a2 c ac a2 c

a a2 c ac a2c

a a a2 e

ac a 2c c

a2 a e

a a2 c c ac

c c ac a2 c e

a a2

ac ac a2 c c a a2 e

a2 c ac c ac a2 e

a

We deduce more. If we let b = ac then b2 = a 2 , b3 = c, b4 = a, b5 = a2 c, b6 = e. We see that G is actually a cyclic group of order 6 which may be represented as either G = (a, c l a3 = e, c2 = e, c -1 ac = a) or

as

G = (b l b6

= e) .

Thus, for a given group, generators and relations are not uniquely determined.

Rem a rk In both of the examples above there were two generators a and c for which a3 = e, c2 = e and one further relation between a and c. We take this opportu­ nity to remark that if we merely have two elements a and c for which a3 = e,

Groups, Rings and Fields

206

= e and no relation is presumed to exist between a and c then it may be shown, but regrettably not easily, that the group so described is isomorphic to the group of linear fractional transformations of the form

c2

az + (3 z --t -'YZ + 8

(a, f3, 'Y, 8 E

Z, a8 - fh

=

1)

where now a and c correspond respectively to the transfor mations

z

1 z+ 1 '

--t - --

1 z --t - . z

In the two examples above we began with a group, the elements of which could be written down or easily obtained, and we have shown how by considering a few (actually, two) of these elements and some relations between them we may, in some sense, 'recover' the group. What is much more usual is to begin with some elements supposed to be the elements of a group and with some relations between those elements and then to investigate the group which these generators and relations describe. We do not assert either that the elements are necessarily distinct or that the relations are completely independent of one another. In these circumstances the reader may wonder whether the resulting algebraic entity is, genuinely, a group. The answer is fortunately in the affirmative since the group of one element { e } will always satisfy any system of generators and relations albeit trivially. The real interest lies in determining the 'largest ' group, up to isomorphism, satisfying the system. Every group has at least one system of generators and relations. We need only write down the elements a, b, c, . . . and the relations formed of products such as a b = c to get a system of generators and relations, but such a system is no more efficient than a Cayley table. We aim to be more economical with any generators and relations for a group.

Notation The group G with generators a 1 , a 2 , and relations r1 is denoted by involve only a l l a2 , rl l r2 , ; s l l s2 , • •

• •

.

• • •

.

=

s 1 , r2

=

s2 ,

•

•

•

where

• • .

(We shall restrict our attention in this text to a finite number of generators and relations. )

Topics in Group Theory

207

Exa m ple 16

(a, b, c l a2 = b2 = c3 = e, ab = ba = c) . What is the group G? We have e = a 2 b 2 = aabb = abab = (ab) 2 = c2 • But c3 = e and so c = e. Then b = a - l = a. Thus, in truth, G is a group of two elements, namely e and a, and a 2 = e. Consequently G = (a l a 2 = e ) .

Let

G=

We now consider some standard examples.

Exa m ples 17

G = (a I an = e) . Then G is the cyclic group of order n generated by a. Let G = (a l . ) . Then G is the group generated by a with an empty set of relations. Thus e, a, a -1 , a2 , a- 2 , are distinct and G is the infinite cyclic

1. Let 2.

. • •

group generated by a. 3. Let G = (a, bl a 2 = b2 = e , ab = ba} . Then G is isomorphic to the Klein four­ group. 4. Let G = (b, f l b4 = e, / 2 = b2 , / - 1 bf = b3 } . Then we see that (b) , the sul:r group generated by b is normal in G and has order 4. (b)/ ::/; (b) but since f 2 = b2 and f 2 is in the centre of G, no coset distinct from either (b) or (b) f is possible. Thus G has order 8. In fact G is the quaternion group of Exercises 4.5, no. 5 with the same b and f and with a = b2 , e = b3 , h = bf, d = b2 f, g = b3 f. 5. Let G = (a, b I a 2 = b2 = e) . Then G is generated by a and b, both of order 2, but no relation connects a and b. The structure of G is not easy to discern but becomes clearer if we make a small change to the generators. Let e = ab. Then we have c-1 = ( ab) -1 = b- 1 a - 1 = ba and then b- 1 eb = babb = ba = e -1 . Hence it follows that G = (b, e l b2 = e, b-1 eb = e-1 } and so G has a normal subgroup (c) which is an infinite cyclic subgroup of index 2. The group is known as the infinite dihedral group. Groups defined by generators and relations appear in many contexts. One context in particular is that of a group of transformations of some regular geo­ metrical object, the transformations preserving the size, shape and location of the object. Under such a group the vertices of the object are permuted amongst themselves and the group is directly a subgroup of the symmetric group on the set of vertices.

Groups, Rings and Fields

208

Consider, for example, the group of transformations of a square with centre 0 and vertices labelled 1 , 2, 3, 4. We may rotate the square about its centre 0

27!"

7r

.

. are multiples . through angles which of 4 = 2. The permutatiOn p = 7r

( 1 2 3 4)

represents a (clockwise) rotation through an angle of 2. 1

2

4

1

4

3

3

2

G

G

2

4

3 The remaining rotations about 0 are p , p , p = e where e is the identity trans­ formation ( e = ( 1)) . The square may also be reflected about an axis of symmet ry, say about a line through 0, parallel to a side, as shown below. 1

2

4

3

4

3

1

2

-B

G

The reflection r is given by r = ( 1 4) (2 3). We now claim that the group G of all such transformations is generated by p and r. Certainly p4 = e, r2 = e and l 7"- {JT = (1 4) ( 2 3) (1 2 3 4) (1 4) (2 3) = (1 4 3 2) = p- 1 , and so G

=

4

( p, T I p

= T

2

= e, T

- 1 pr = p - 1 )

but we have to establish that every transformation is indeed in G. We confine our considerations to just one further transformation, leaving the reader to ponder the remaining possibilities. We examine the reflection (1 3) about the diagonal joining 2 and 4. 1

2

3

2

4

1

G

209

Topics in Group Theory

Then (1 3) = (1 4 3 2) (1 4)(2 3) p - 1 r E G. We have now proved that the group of transformations preserving a square is a group which previously we called the dihedral group D4 of order 8. We may extend these arguments to consider the group of transformations of a regular polygon . If the polygon has n vertices, labelled 1, 2, . . . , n, then it may be =

rotated through angles which are multiples of

2 rr , n

thus yielding the trans­

formation p = ( 1 2 . n ) and powers of p. The polygon may also be reflected about an axis of symmetry through its centre. If n is even, n = 2N ( say) , the axis of symmetry may be chosen ( as in the case of the square ) to be the perpendicular bisector of the side joining 1 and 2N. We then have a reflection r = (1 2N) (2 2N - 1) . . . (N N + 1). As p = ( 1 2 . . . 2N) we have T - 1 pr = p-1 . .

.

If n is odd, n = 2N + 1 ( say) , the axis of symmetry must pass through one vertex 2N + 1 ( say) and we have a reflection r = (1 2N)(2 2N - 1) . . . (N N + 1) . Since p = ( 1 2 . . . 2N + 1) we have /N+ l = r 2 = e, r - 1 pr = p- 1 • In both cases we may show that the group generated by p and r contains all transformations of the polygon. In summary, we have shown that the group of transformations of a regular n-gon is n ( p, T I p = T 2 = e, T- 1 pT = p- 1 ) which is called the dihedral group Dn of order 2n. Exercises 6. 2

1. 2. 3. 4. 5. 6.

Let G = (a, b I a3 Let G = (a, b I a4

=

b2

=

e, ba = e) . What is the order of G?

e , aba2 = b) . Prove that G has order 2. Let G = (a, b l a8 = e, a4 = b2 , b -1 ab = a - 1 ) . Prove that G has order 16 and that G has only one subgroup of order 2. Prove that G = (a, b l a3 = b2 = e, b - 1 ab = a- 1 ) is isomorphic to the 83 and that G is also the group of transformations preserving size etc. of an equilateral triangle. ( See Exercises 6.1 , no. 9.) =

b2

=

What i s the group of transformations preserving size etc. o f a rectangle which is not a square? Prove that all transformations preserving size etc. of a regular penta­ gon may be identified with elements of the dihedral group D5 .

Groups, Rings and Fields

210

6.3 Direct Products and Sums

Let G be the cyclic group of order 6 generated by a, G = (a l a6 = e) .

=

G has two proper subgroups, namely P { e, a3 } and Q = { e, a, a2 } of orders 2 and 3 respectively. These subgroups are normal in G and we obviously have PnQ = { e} and PnQ = G. We describe this situation more generally in the following definition.

Defi n ition 1 1

=

Let G be a group. Let H and K be normal subgroups of G such that the inter­ section HnK { e} and G = HK . Then G is said to be the (internal} direct product of H and K .

=

Let us now consider two groups A and B where A = (a l a2 e A ) and B = (b l b3 = e8) , eA and e8 being the identities of A and B, and A and B are cyclic groups of orders 2 and 3 respectively. Let G be the Cartesian product A x B of A and B, then G {(eA , eB) , (eA , b) , (eA , b2 ) , (a , e8) , (a, b) , (a, b2 ) } .

=

Let the multiplication in G be component-wise so that , for example, (eA , b) (a, b) = (eA a , bb) = (a, b2 ) . Then under this multiplication it may b e seen that A generally, we describe this situation in a definition.

x

B is a group. Again, more

Defi n ition 12 Let G be the Cartesian product of the groups A and B. A multiplication is defined on G = A x B by (a, b) (a', b' )

= (aa' , bb' ) .

Then G is a group called the (external) direct product of A and B.

= A B we notice that A = { (a, eB) i a E A} and B = { (eA , b) l b E B}

In the group G

x

are normal subgroups of G and that the mappings a --t (a, e8)

(a E A) and b

--t

(eA , b)

(b E B)

Topics in Grou p Theory

211

B.

B

yield isomorphisms of A with A and B with respectively. Moreover G is the (internal) direct product of A and Both of the definitions above extend naturally to direct products involving a finite number of subgroups or groups.

Defi nition 13

Let G be a group. Let Hl > H2 , , Hn be normal subgroups of G such that H; n H1 H2 H; - l Hi+ l . . . Hn = {e} (i = 1 , 2, . . . , n ) and G = H1 H2 Hw • • •

•

•

•

• •

•

Then G is said to be the (internal) direct product of H1 , H2 , . . . , Hn. In this definition, since H1 , H2 , . . . , Hn are normal subgroups of G, it follows that, for each i, 1 :=:;; i :=:;; n, H1 H2 H; _ 1 Hi+ 1 . . . Hn is a normal subgroup of G. . • •

Defi nition 14

Let G be the Cartesian product of the groups A 1 , A2 , . . . , An. A multiplication is defined on G = A 1 x A2 x . . . x An by ( a l l � ' . . . , a n) (a � , a ; , . . . , a �) = (a 1 a � , a2 a; , . . . , ana � ) (a; , a: E A; , i = 1 , 2, . . . , n )

Then G is a group called the (external} direct product of A 1 , A2 , Similarly,

as

• . •

, Aw

above, A; = { (e 1 , e2 , . . . , ei - 1 > a, ei + l • . . . en) I a E A ; } ,

where Ai h as the identity ei (j = 1 , 2, . . . , n } , is isomorphic to A; (i = 1 , 2, . . . , n } and G is the (internal} direct product of A 1 , A2 , , Aw On account of these obvious isomorphisms we sometimes do not always draw a precise distinction between internal and external direct products. • • .

Definition 15 Let p be a prime. A group the order of which is a power of p is called a p-group.

Defi nition 16 Let p be a prime. Let H1 , H2 , . . . , Hn be cyclic groups of order p. Any group iso­ morphic to the direct product H1 x H2 x . . . x H n is said to be an elementary p-group.

Groups, Rings and Fields

212

Exa m ple 18

The Klein four-group is an elementary Abelian 2-group. We have given the definitions above for groups having a binary operation of multiplication. If we are concerned with Abelian groups then, as we know, an additive notation is commonly employed. The changes of notation and nomen­ clature are fairly obvious. We may still form the Cartesian product of Abelian groups to obtain an additive group in which addition is performed component­ wise, yielding an (external} direct sum. We find it to be convenient now to rephrase the definition above for (internal) direct s ums of Abelian groups.

Defi n ition 17 (following Definition 13)

Let A be an Abelian group. Let A 1 , A2 , . . . , An be subgroups of A such that A; n (A1 + A2 + . . . + A ; - 1 + A i+l + . . . + A n) = {0} (i = 1, 2, . . . , n )

and A = A1 + A2 + . . . + An- Then A is the (internal) direct sum of A� > A2 , · . . , An .

Exa m ples 19

1. Let A, B and C be groups of orders 9, 14 and 18 respectively. Then the group G, given by G = A x B x C, is a group of order 9 . 14.18 = 2268. 2. Let A, B, C be cyclic groups of orders 7, 8 and 17 respectively. Then the group G, given by G = A x B x C is a group of order 952. Moreover if A = (a l a7 = eA ) , B = (b l b8 = e B ) and C = (c l c1 7 = e c )

then G is cyclic with generator ( a, b, c) and identity element ( e A , e B, e 0 ) . Exercises 6. 3

1 . Let A, B and C be normal subgroups of a group G. Prove that ABC is a normal subgroup of G.

2. Let the group G be the direct product of the groups H and K. Prove that G is Abelian if and only if H and K are Abelian. 3 . Let H and K be normal subgroups of a group G such that G = HK. Prove that G/( H n K) is the direct product of H f( H n K) and Kf( H n K) . 4. Let A, B and C be subgroups of an Abelian group G such that

G = A + B + C, A n B = {0} , A n C = {0} and B n C = {0} .

Does it follow that G is the direct sum of A , B and C?

213

Topics in Group Theory

6.4 Abelian Groups The structure of an Abelian group may be very complicated and, without some conditions on the group, may be difficult to determine. If the group has a finite number of generators then a structure theorem is possible. Here we shall further restrict the considerations to finite Abelian groups for which we obtain a struc­ ture theorem. We have shown that a cyclic group has subgroups of all possible orders and that the order of an element in a group is the order of the cyclic subgroup generated by that element . If the order of every element of a group is a power of a prime p then it is not immediate, at present , that the group is a p-group since the order might be divisible by some prime other than p and yet have no elements of that order. One of our aims is to eliminate this hypothetical situation. We begin with a lemma which resolves the situation for an Abelian group. As is customary we shall employ additive notation when discussing Abelian groups.

Lem ma 5

Let A be a finite Abelian group. Let p be a prime such that every element of A has an order which is a power of p. Then A is a p-group.

P roof If A is cyclic then, by the remarks above, A is a p-group since if I A I is divisible by a prime q, q f. p, we would have an element of order q, which is false. We may now argue by induction and assume the result is true for all groups of orders strictly less than I A I · Suppose A is not cyclic and let a E A, a =/:- 0. Then the subgroup (a) generated by a has an order which is a power of p. Further, A/ (a) has the property that every element has an order which is a power of p since if x E A and x has order p 0 then

p0 (x + (a)) = p 0 x + (a) = 0 + (a) = (a) and so x + (a) has order dividing p 0 • By the induction assumption Aj(a) is a p-group and so, as I A I = l (a) l = l (a) I I A/(a) l, A is a p-group. This completes the proof.

0

Theorem 8 Let A be a group of order where p� 1 p�2 p�n where p1 , P2 , . . . , Pn are distinct primes and ai > O (i = 1, 2, . . . , n ) . Let Ai = {x E A i pf;x = O } •

•

•

Groups, Rings and Fields

214

(i = 1 , 2, . . . , n ) . Then Ai is a subgroup of order pf' direct sum of At , A2 , . . . , An .

(i = 1 , 2,

.

. . , n ) and A is the

Proof , n .

Ai is a Pi-subgroup of A (i = 1, 2, . . . ) We want to show that A = A t + A2 + . . . + An, Ai n ( A t + A2 + . . . + Ai - l + Ai + l + . . . + A n) = {0} (i = 1 , 2, . . ) ) and finally that I Ai I = pf' (i 1, 2, f ) Since p1 , p2 , . . . , Pn are distinct Let qi be given by I A I = p ' qi (i = 1, 2, primes, qt , q2 , . . . , qn have 1 as their greatest common divisor. Hence there exist t t , t2 , . . . , tn E Z such that t tqt + t2 q2 + + tnqn = 1 . Then, if x E A, X = t tqt X + t 2 q2 x + . . . + tnqnx E A t + A 2 + . . . + A n ) since pf' q ix = I A l x = 0 implies that q ix E Ai (i = 1 , 2,

By Lemma 5,

. , n

. . . , n .

=

. . . , n .

·

· ·

. . . , n .

Let now

y

E Ai n (A t + A2 + . . . + Ai- t + Ai + l + . . . + An)

for some j E { 1 , 2, . . . , n } . Since y E Ai we have p;i Yi = 0. On the other hand, since y E A t + A2 + . . . + Aj t + Aj + t + . . . + An we have

+ Y2 +

+ Yi - 1 + Yi + l + + Yn where Yk E A k (k = 1, 2, . . . , j - 1, j + 1, ) Then + %Yi - 1 + %Yi+ t + + %Y n = 0 + 0 + %Y = %Y 1 + qj Y2 + Y = Y1

·

· ·

·

· ·

· ·

·

. . . n .

· · ·

· ·

.

+ 0 = 0.

Thus the order of y divides the coprime integers pj and

qj and so y = 0. Thus Ai n (A t + A2 + . . . + Ai - t + Ai + t + . . . + An) = {0} (j = 1 , 2, . . . , } . Hence A is the direct sum of A t . A2 , . . . , Am and so I Ad (i = 1, 2,

Since

is a power of Pi (i = 1, 2, . . . , n ) we deduce that ) and our proof is now complete.

. . . , n

n

I Ad

= pf' 0

By virtue of this last theorem we need only consider the structure of a finite Abelian p-group. The following rather obvious lemma is useful.

215

Topics in Group Theory

Lem ma 6

Let G be a group. Let H1 , H2 and K be subgroups of G such that K is a normal subgroup of G and K k H1 n H2 . If Ht f K n H2 / K is the trivial subgroup of G/K then K H1 n H2 . =

P roof Let x E H1 n H2 . Then Kx E Ht f K n H2 / K and so, by assumption, Thus x E K giving the result.

Kx = K. D

Lem ma 7

Let A be a finite Abelian p-group. Let a be an element of A of greatest possible order. Then there exists a subgroup H of A such that A is the direct sum of H and (a).

P roof If A is cyclic then A = (a) and the result is true with H = { 0 } . Suppose A is not cyclic. We shall argue by induction on the order of A, assuming that the result is true for groups of orders strictly less than I A 1 Then a is of greatest possible order p m , say, in A and A f. (a) . We claim that there exists in G \ (a) an element of order p. We choose b E G \ (a) to have least possible order amongst the elements of G \ (a). If pb = 0 then our claim is proved. If pb f. 0 then b has order p r where p < p r < p m . But then pb has order p r - l and so, by the choice of b, pb E (a). Thus pb = na for some n E Z and hence

0 = pr b = pr - l (pb) = p r - \na) = (pr - l n)a. l Since a has order p r it must be that pr divides p r - n and so p divides n. Thus n = pq for some q E Z. Let c = b - qa. Since b ¢ (a), we necessarily have c ¢ (a). But pc = pb - pqa = pb - na 0 and so c E A \ (a) and c has order p. =

This proves our claim. We may now suppose that b has order p. Then (b) n (a) = {0 } since (b) n (a) f. 0 implies (b) k (a) which is false. Then a + (b) has order pm in Af (b) and so a + (b) is an element of greatest possible order in A/ (b). By the induction assumption there exists a subgroup such that A/ (b) is the direct sum of this subgroup and ( (a) + (b))/(b). We may write the subgroup in the form H/ (b) for some subgroup H of A.

Groups, Rings and Fields

216

(b) � H, A = H + ((a) + (b)) = H + (a) . In addition we have (( a) + (b)) = (b) . To complete the proof we have to show that H n (a) = { 0} . Let , therefore, X E H n (a) . Then X E H n ((a) + (b)) = (b) . Thus X E (a) n (b) = {0} and we Then, as

Hn

have established the lemma.

D

Corollary A finite Abelian p-group is a direct sum o f cyclic p-subgroups.

P roof Let A be a finite Abelian p-group. By Lemma 7 there exists a cyclic subgroup A 1 and a subgroup H such that

A = A1 + H, A1 n H = { 0}. Now H has strictly lower order than A and so a simple induction ensures that H is a direct sum of cyclic p-groups A2 , A , . . . , A n , say. 3 Thus

and and so, finally,

A is the direct sum of A 1 , A2 , . . . , A n .

D

We are now able to prove our main theorem on the structure of finite Abelian groups.

Theorem 9 F u nda menta l Theorem of Finite Abelia n Groups

A finite Abelian p-group A is direct sum of cyclic p-subgroups. If A is a direct sum of the cyclic p-subgroups A1 , A2 , , A m and is also the direct sum of the cyclic p-subgroups B1 , B2 , . . . , B n then m = n and, with a suitable renumbering if necessary, A1 is isomorphic to B; (i = 1 , 2, . . . , n ) . .

.

•

Proof The Corollary above yields the first statement of the theorem. We now prove the second statement. First of all, let A be an elementary Abelian p-group. Then all non-zero elements of A have order p and so any cyclic subgroup of A has order p.

Topics in Group Theory

217

Thus since A is the direct sum of cyclic subgroups A1 , A2 , . . . , A m and of cyclic subgroups B1 , B2 , . . . , B n each of these subgroups has order p and so

A m i = I A I = I B1 B2 p m = I A 1 A2 Thus m = n and the result holds. X

X . . . X

X

X . . . X

Bn l = p n .

We shall argue by induction and we make the assumption that the result is true for all Abelian p-groups of orders strictly less than I A 1 . Let now A be not an elementary Abelian p-group. Suppose the notation is chosen so that A 1 , A2 , . . . , A r are cyclic groups of orders � p2 and A r+ l • A r+ 2 , . . . , A m are cyclic p-groups of orders p ( 1 < r � m ) . Similarly suppose the notation is chosen so that B1 , B2 , . . . , B. are cyclic subgroups of orders � p2 and Bs + 1 , Bs + 2 , . . . , Bn are cyclic p-groups of orders p ( 1 < s � n ) . Letting pA be the subgroup {pa l a E A} (that this is a p-subgroup is easily verified ) we have, in an obvious adaptation of this notation, X

X . . . X

X

X . . . X

pA = pA l pA2 pA l pA2 =

X

X . . . X

X

X . . . X

pA r pA r+ l pA r ,

pA m

and X

X . . . X

pBn pB8 pB8 + 1 pA = pBl pB2 = pBl pB2 pB By induction r = s and, with a suitable renumbering if necessary, pA; is iso­ morphic to pBi (i = 1 , 2, . . . , r ) . Hence Ai is isomorphic to B; (i = 1 , 2, . . . , r ) . Thus the direct products A 1 x A2 x . . . x A r and B1 x B2 x . . . x Br are X

X . . . X

•.

isomorphic. But then

I A r+ l x A r+ 2 x . . . x A m i = I A : A1 x A 2 x . . . x A r l Br I = I A : B1 B2 = I Br + l Br + 2 · Bn l · n r r Hence p m - = p - and so m = n and this completes the proof. X

X

X . . . X X

·

·

X

D

Exercises 6. 4

A be an Abelian group. Let M be the set of elements of A of finite order. Prove that M is a subgroup of A and that Aj M contains no non-trivial elements of finite order.

1 . Let

A be an Abelian group. Let is a subgroup of A.

2. Let

n

E N. Prove that n A = { na I a E A}

Groups, Rings and Fields

218

3. Up to isomorphism find all Abelian groups of order 20 . 4. Up to isomorphism find all Abelian groups of order 72. 5. Up to isomorphism find all Abelian groups of order 2250 .

6 . 5 p-Groups and Sylow Subgroups From the Fundamental Theorem of Abelian Groups every Abelian group of order p� 1 p�2 p�n , where p1 , P2 , . . . , P n are distinct primes and O:; > 0 (i = 1 , 2, . . . , n ) , has a subgroup of order p �; (i = 1 , 2, . . . , n ) . We have here a number-theoretic relationship between the order of an Abelian group and of the orders of certain subgroups of the group. We develop this relationship for non-Abelian groups but first we must investigate p-groups. We begin with a useful counting result. •

•

•

Theorem 10

Let G be a finite group. Let Z(G ) be the centre of G and let C1 , C2 , . . . , C N be the conjugacy classes of G, each of which contains at least two elements of G. Let X r E cr and let Cc(x r ) be the centralizer of X r in G (r = 1 , 2, . . . , N) . Then I G I = I Z(G) I

N

+ L I G : Cc(x r ) l . r= l

P roof Z(G ) consists of those elements of G which are self-conjugate. Thus G = Z(G )

U C1 U C2 U . . . U CN

is a disjoint union. By the Corollary to Theorem 20, Chapter 4, the number of elements in cr is given by I G : Cc(x r ) I and so, from the disjoint union above, I G I = I Z(G ) I

Theorem 1 1

n

N

+ L I G : Cc(x r ) l . r= l

D

Let G be a finite group of order p (n � 1) where p is a prime. Then the centre Z(G ) of G is non-trivial.

219

Topics in Group Theory

P roof In the notation of Theorem 10, we have I G : Cc (xr) I > 1 and, necessarily, I G : Cc(x r ) I divides I G I . Thus since I G I = p n we deduce that p divides I G : Cc(x r ) I , r = 1 , 2, . . . , N. Hence p divides E;:'= l I G : Cc(x r ) I · Thus as N

I G I = I Z ( G ) I + L IG : Cc(x r ) l r= l we conclude that p divides I Z ( G) I and so we obtain the result . pn =

D

vVe give some examples showing the importance of Theorem 1 1 .

Exa m ples 2 0

1 . Let G be a group of order p2 where p is a prime. Then we may prove that G is

Abelian as follows. Certainly we now know that the centre Z ( G ) of G is non­ trivial and so must be of order p or p2 • But if Z ( G) is of order p then GI Z ( G) is also of order p and so is cyclic. By Example 2 5 no. 3 of Section 4 . 4 G is then Abelian. A group of order p3 need not be Abelian. Both the quaternion and dihedral groups of order 8 are non-Abelian. 2. Let G be a group of order p n (n :;::: 1) where p is a prime. Then we assert that G contains a normal subgroup of index p. We know that Z ( G) =/:. {e}. If Z ( G) = G then G is Abelian and the reader should verify that the assertion follows from the Fundamental Theorem of Abelian Groups. We suppose therefore that Z ( G) =/:. G and we intend to argue by induction on I G I · Thus by the induction assumption GI Z ( G ) has a normal subgroup of index p. By Exercises 5.4, no. 4 , the normal subgroup of index p may be written as H I Z ( G ) where H is a normal subgroup of G. Then I GI Z ( G ) : HI Z ( G ) I = p implies that

and so

IG : HI

1 =1

I Z ( G) I = p IGI I Z (G ) I IHI X

�: = p, proving the assertion.

We come now to the first of two major and fascinating theorems on the struc­ ture of finite groups. Insofar as this text is concerned they will represent the cul­ mination of our work in group theory. A.-L. Cauchy (1 789- 1857) proved that every group of order pa m, where p is a prime not dividing m, contains a subgroup of order p, but it was P .L. Sylow (1832-1918) who established the existence of a subgroup of order pa and which was subsequently named after him.

Groups, Rings and Fields

220

Theorem 12 (Sylow)

Let G be a finite group of order p a m where p is a prime not dividing m. Then G has a subgroup of order p a .

Proof If G is Abelian the result has already been shown. Suppose G is non-Abelian and make the induction assumption that the result is true for all groups of orders strictly less than I G I · In the notation of Theorem 10 we have N

I G I = I Z(G ) I + L I G : Cc(x r ) I · r= l We consider two cases. If p divides I G : Cc(x r ) I for r = 1 , 2 , . . . , N then p divides I Z(G ) I · But then Z(G ) has a subgroup Q of order p b where 1 :<:; b $ a. Since Q is a subgroup of the centre of G, Q is normal in G and so we may form G/ Q which has order p a - b m. By the induction assumption G/Q has a subgroup of order a - b. p We let PJQ be this subgroup. Then I P/Q I = pa - b and so I P I = I P /Q I I Q I = pa - bpb = pa , proving the result. On the other hand, if p does not divide I G : Cc(x r ) I for all r E { 1 , 2, . . . , N} then we may suppose that p does not divide I G Ca (x;) I , say. Then I Cc(x;) I = pa n for some proper divisor n of m. By the induction assumption Cc (x;) has a subgroup of order pa . The proof is now complete. D a

p m =

:

Defi n ition 18

Let G be a finite group of order p a m where p is a prime and p does not divide m . Then a subgroup of G of order p a is called a Sylow �subgroup of G. We note that a Sylow p-group of G has the greatest possible order of all p-subgroups of G.

Exam ples 2 1

4 1 . A group G of order 8897850 = 2.3 .5 2 . 133 has Sylow subgroups corresponding to the primes 2, 3, 5 and 13. These Sylow subgroups have orders 2, 8 1 , 25 and 2 197 respectively. 2. Let us examine the Sylow subgroups of the symmetric group S4 • The order of the S4 is 4! = 4.3.2. 1 = 24 = 23 .3. The subgroup V = { ( 1 ) , ( 1 2 ) ( 3 4 ) , ( 1 3 ) ( 2 4 ) , ( 1 4 ) ( 2 3 ) } is a normal subgroup of order 4, and is a Klein four-group. V is contained in every Sylow 2-subgroup. There are, in fact,

22 1

Topics in Group Theory

exactly three Sylow 2-subgroups which are V U V{ 1

2) , V U V{1

3) and V U V{ 1

4) .

One Sylow 3-subgroup is P = { { 1 ) , ( 1 2 3), {1 3 2) } . The normalizer of P, Nc ( P ) , is given by Nc (P) = P U P{ 1 2) = { {1 ) , {1 2 3) , { 1 3 2) , { 1 2) , {1 3) , {2 3) } . We obtain a coset decomposition

S4

=

Nc (P) U Nc {P) {1

4) U Nc(P) (2 4) U Nc(P) {3 4) .

There are exactly four Sylow 3-subgroups which are P, {1

4r 1 P(1

4) , {2 4) - 1 P (2 4) , {3 4)-1 P ( 3 4) .

Lem ma 8 Let P be a normal Sylow p-subgroup of the finite group G. Let Q be a p-subgroup of G. Then Q � P.

P roof Since P is normal in G, PQ is a subgroup of G. Since PQ / P is isomorphic to Q/ (P n Q) it follows that I PQ/P I = I Q/ (P n Q) I and so I PQ/P I is a power of p. Thus PQ is a p-subgroup of G. But P � PQ and P is a Sylow p-subgroup of G. Thus P = PQ and so Q � P. 0

Corol la ry Let P be a Sylow p-subgroup of the finite group G. Let Q be a p-subgroup of the normalizer Nc ( P) of P. Then Q � P.

P roof P is a normal Sylow p-subgroup of Nc (P) . Since Q � Nc ( P) we deduce, from Lemma 8, that Q � P. D We have now reached the second of Sylow's famous theorems.

Theorem 13 (Sylow)

Let G be a finite group of order pa m where p is a prime and p does not divide m. Then the Sylow p-subgroups of G form a complete set of conjugate subgroups of G and if their number is n then n = I G : Nc {P) I and n = 1 (mod p) .

Groups, Rings and Fields

222

Proof , P n } be a complete set of Let P be a Sylow p-subgroup of G and let { Pt , P2 , conjugate Sylow p-subgroups of G. Part of what we are required to show is that , of necessity, P E { Pt , P2 , . . . , P n }· , P n } if we define Now, evidently, P acts as a permutation group on { Pt , P2 , t for x E P, x.P; = xP;x- (i = 1 , 2, . . . , n) . By Theorem 6, this action defines an equivalence relation "' on { Pt , P2 , . . . , P n } · Consider P; . We want to calculate the number of Pt , P2 , , Pn in the same equivalence class of P; . In other words we want to know the number of elements in the orbit containing P; . But, by Theorem 6, this number is I P : Stabp ( P; ) I where Stabp ( P;) is the stabilizer of P; under the action of P. We have 1 Stabp(P;) = {x E P l x.P; = P; } = {x E P l xPix- = P; } • • •

.

•

=

•

.

•

•

{x E P i x E Nc (P;) }

=

P n Nc ( P;) ,

where Nc (P; ) is the normalizer of P; in G. But I P : Stabp (P;) I is a power of p and hence I P : Stabp (� ) I = 1 if and only if P = Stabp (P; ) = P n Nc( P; ) · But this is possible if and only if P � Nc (P;) which, according t o Lemma 8 , would imply that P � � and so P = P; . We may draw two conclusions from this argument . If we have P rt { Pt , P2 , , Pn } then for no i is I P : Stabp (P;) I = 1 and so the number of elements in each orbit is divisible by p and hence n = 0 (mod p) . On the other hand we may certainly choose P from {P1 , P2 , . . . , Pn } , say we choose P = P1 . Then in this case the number in the orbit containing Pt is precisely 1 but the numbers of elements in each of the remaining orbits is divisible by p and thus , Pn } , we n = 1 (mod p) . Thus if we are able to choose P not in { P1 , P2 , have n = 0 (mod p) and n = 1 (mod p). Thus we have a contradiction which is only resolved if we cannot choose P not in { P1 , P2 , , Pn } · It follows therefore that the set { Pt , P2 , , Pn } is the complete set of Sylow p-subgroups and these are therefore conjugate to one another. Furthermore we have n = 1 (mod p) . That n = I G : Nc (P) I is obvious and the result is proved. 0 .

•

•

•

.

.

• • •

•

Exa mples 22

•

•

1. Let us prove that a group G of order 1 75 is necessarily Abelian. From the fac­ torization, 1 75 = 52 .7, the group G has Sylow 5-subgroups of order 25 and Sylow 7-subgroups of order 7. Suppose there are m Sylow 5-subgroups and n Sylow 7-subgroups. Then m divides 5 2 .7 and m = 1 + 5r for some r E {0, 1, 2, . . . } . If r > 0 then m must divide 7 which is impossible. Thus r = 0 and m = 1 . Also n divides 5 2 . 7 and n = 1 + 7s for some s E { 0 , 1 , 2, . . . } . If s > 0 then n must divide 5 2

Topics in Group Theory

223

which is impossible. Hence the Sylow 5-subgroup P and the Sylow 7-subgroup Q are both unique. Thus G is isomorphic to the direct product P x Q and is therefore Abelian as P and Q are Abelian. 2 . Let G be a finite group and let P be a Sylow p-subgroup of G. Let H be a sub­ group of G such that Nc (P) <;;:; H. We assert that Nc (H) = H. The proof of the assertion exemplifies a common trick in regard to using Sylow subgroups. Let x E G be such that x- 1 Hx = H. Then we wish to prove that x E H. Certainly x- 1 Px <;;:; x- 1 Nc (P)x <;;:; x- 1 Hx = H. 1 Then P and x- Px are both Sylow p-subgroups of H. Then the trick is to invoke Theorem 13 and to observe that P and x- 1 Px must be conjugate in H (and not merely in G) . Thus we have h E H such that h- 1 Ph = x- 1 Px. But then 1 P = hx- 1 Pxh- 1 = (xh- 1 ) - 1 P(xh- ) and so xh- 1 E Nc (P) <;;:; H from which x E Hh = H, completing the proof. Exercises 6. 5

l .Let G be a p-group. Let H be a proper subgroup of G. Prove that H is not equal to its normalizer in G. Deduce that any subgroup of G of index p is normal in G. 2. Prove that groups of orders 45 and 207 are Abelian. 3. Let P be a Sylow p-subgroup of a finite group G. Let N be a normal subgroup of G. Prove that P n N is a Sylow p-subgroup of N and that PN/ N is a Sylow p-subgroup of Gj N. (Hint: use the Second Isomorphism Theorem.) 4 . Prove that a group of order pq where p and q are primes has a proper normal subgroup. 5. Let G be a group of order 60. How many Sylow 5-subgroups may such a group have? 6. Prove that a group of order 35 1 has either a normal Sylow 3-subgroup or a normal Sylow 13-subgroup.

Hints to Solutions

1.1

1 . A U B = {u, v, w, x, y} , A n B = {w}, A n C = 0 , A \ B = {u, v}, B \ A = {x, y}, A' = {x, y, z} , A \ (B u C ) = {u, v}, (A n B) u (B \ A) = {w, x, y} . 2. (X n Y)' = { a, c, 1 , 2, 3} = X' U Y ' , (X U Z)' = 0 = X' n Z ' . 3. A U X = {2, 4} implies 1 , 5 ¢ X. A U X = { 1 , 2, 4, 5, 6 } implies 6 E X. X = {2, 4, 6}. 4. A <::::: B implies B <::::: A u B <::::: B u B = B. 5. No rule is given. A could be either or neither. 6. k; choices for elements of A; (i = 1, 2, . . . , n ) . 1.2

1. (i )

Shaded area represents

(A U B)' and A' n B'. 225

Groups, Rings and Fields

226

( ii ) 2. ( i )

x E (A u B)' implies x ¢ A U B and so x ¢ A, x ¢ B. Thus x E A' , x E B' and x E A' n B'. y E A' n B' implies y E A', y E B '. Thus y ¢ A, y ¢ B and so y ¢ A u B and y E (A U B) '.

Shaded area represents A U (B n C ) and (A U B) n (A U C) . ( ii ) X E A u ( B n C) implies that X E A or X E B n C. But X E A implies that X E (A u B) n (A u C). X E B n c implies X E B, X E c and so it follows that X E (A u B) n (A u C). y E (A u B) n (A u C) implies y E A U B and y E A U C. If y E A then y E A U (B n C ) . If y (j. A then y E B and y E C and so y E B n C. Thus y E A U (B n C).

A = { 1 , 2}, B = C = { 1 } . If A � C then A U (B n C) = (A U B) n (A U C ) = (A U B) n C. If (A U B) n (A U C) = (A U B) n C then A = A n A � (A U B) n (A U C ) = (A U B) n C � C.

3 . No. Try

4. Draw a Venn diagram. Let E, B, S be the sets of readers of the Economist, the Bangkok Post and the Straits Times respectively. I E U B U S I = l E I + I B I + I S I - I E n B I - I E n S I - I B n C l + l E n B n S l = 250 + 41 1 + 3 1 5 - 72 - 51 - 31 + 1 = 823. 1000 - 823 = 1 77 do not read any of the publications. 5. Draw a Venn diagram. Let I, S, L be the sets of children who like ice cream, sweets and fizzy lemonade respectively. I I n S n L I = 31 , I I n L I = 36, I (I n L) \ (I n S n L) I = 5, I I n S' I = 7, l i n (S u L) ' I = 2, I S n L I = 80, 1 (S n L) \ (I n s n L) 1 = 49, I L n (I u S ) ' l = 149 - 5 - 31 - 49 = 64, l S I = 1 10. Hence I I U S U L l = 1 1 0 + 2 + 5 + 64 = 181 . 200 - 181 = 19 dislike all three items.

Hints to S o luti o ns

227

1.3

1 . ( g o !) (a) = 0 , (g o f)(b) = (g o f)( c) = 1 . 2. Only q o p is defined. 3. (! o g) (n) = 6n + 1 0, (g o f)(n) = 6n + 5 , (! o h) (n) = - 12n, (h o f)n = -1 2n, (g o h) (n) = - 18n + 5 , (h o g) (n) = - 18n - 30. 4. (i) If g(f(a) ) = g(f(a')) (a, a' E A) then f(a) = f(a') and then a = a'. (ii) If f(a) = f(a') then g(f(a)) = g(f(a')) and so a = a'. E C. If there exists a E A such that (g o f)(a) (iii) Let then But if A = C = {1, 2 } , B = {1, 2, 3} and f(1 ) = 1 , g(f(a)) f(2) = 2, g(1) = 1, g( 2) = g(3) = 2 then g o f is bijective, g is not injective and f is not surjective. 5. (i) If x E f(A) , x = f(a) (a E A), A � B and so x E f(B) . (ii) A � A U B implies f(A) U f(B) � f(A U B) . If x E f(A U B) , then x = f(u) (u E A U B). If u E A then f(u) E f(A) and if u E B then f(u) E f(B) . ThlL� u E f(A) U f(B) . (iii) A n B � A, etc. 6. n2 - 3n + 5 = 3 if and only if n = 1 , 2. f(1 ) = f(2) = 3. A n B 0 and f(A n B) = 0. c

= c,

= c.

=

1.4

. lies a2 = c-2 . . 1"1es b2 = a2 . a2 = b2 , b2 = 2 rmp 1 . a 2 = a2 . a2 = b2 rmp 2 . a "' a since a - a = 0 . a "' b , a - b even, b - a even , b "' a . a "' b, b "' a - b, b - even , a - = (a - b) + (b - ) a - even, a "' 3. a "' a since 6 divides 0 = a - a, etc. 4 . For each q E Q, equivalence class {q + x lx E Z}. c

c

c

c ,

c

c.

c,

5. (i) Yes. Equivalence class is straight line through 0. (ii) Yes. Equivalence class is circumference of circle , centre at 0.

6.

Recall that an equivalence relation corresponds to a partition.

X = {x} : {x}. One relation. X = {x , y} : {x} , {y} ; { x , y} . Two relations. X = {x , y , z} : {x} , { y} , { z} ; {x , y} , { z} ; {x , z} , {y} ; {y, z} , {x} ; {x , y, z} . Five

relations.

228

Groups, Rings and Fields

X = {x, y, z, t}: {x }, {y}, {z}, { t} ; {x, y}, { z} , { t} and five other similar par­ titions; {x, y}, {z, t} and two other similar partitions; {x, y, z }, {t} and three other similar partitions. Fourteen relations. 5 divides 14 - 9, 7 divides 9 - 2 but neither 5 nor 7 divides 12 - 2. p is the equivalence relation corresponding to the partition {a, b, c}, {x }, {y}, {z}. a is not an equivalence relation since xaa, aay but xay i s false. We do not necessarily have a "' a for all a E S.

7. No. 8. 9.

1.5

1 1 . 1 (1 + 1) = 3 1 (1 + 1 ) (1 + 2) . n+ 1

n

r= 1

r=1

L r(r + 1 ) = L r(r + 1) + (n + 1)(n + 2)

�

1 = 3 n(n + 1)(n + 2) + (n + 1 ) (n + 2) 1 = 3 n(n + 1 ) (n + 2) (n + 3)

2. 1 3 = 1 2 (1 + 1) 2 • n+ 1

1 1 L r3 = 4 n2 (n + 1 ) 2 + (n + 1) 3 = 4 (n + 1) 2 (n + 1) 2 •

r=1

3.

0 1 -a a # 1 , a = --. 1 -a 1 - an n 1 - an + 1 � ar-1 = -L.J 1-a +a = 1 -a r=1

---

1 1 4• 1 (1 + 1) - 1 + 1 " n+ 1 1 = n 1 n+ 1 = + r(r + 1 ) n + 1 (n + 1) (n + 2) n + 2 " 1 5. (5 - 2) = 2 (5 + 1) . n+ 1 n 1 L ( 5r - 2) 2 (5n + 1) + [5(n + 1) - 2] = 2 (n + 1 ) [5(n + 1) + 1].

b r= 1

=

Hints to Solutions

nLl r r=l

229

6. 2 = 2. +

r2

7. 1

= 2 + (n - 1 ) 2 n + I + (n + 1 ) 2 n + l = 2 + n2 n + 2 •

+ x ;::: 1 + x. (1 + xt + 1 ;::: (1 + nx) ( 1 + x) = 1 + (n + 1 )x + x2 ;::: 1 + (n + 1 )x.

8. 3(6. 2 + 1 ) = 39 � 26 • Then n ;::: 6, 3[2(n + 1) + 1] = 3(2n + 1) + 3.2 �

n

2n

+ 3. 2 �

2n 2n 2n + l . n 2n n +

9. 3.8 2 = 3.26 � 22 . 26 = 28 • Then n ;::: 8, 3( n + 1 ) 2 = 3n2 + 6n + 3 � 2 + 3(2n + 1 ) � 2 +

� implies 2( ../2 - 1 ) � �-

1 0 . ../2 �

n2:+l r=l

1

r- ;::: 2( Vn+l - 1 ) + r

y

1 n+ 1

[

1 1 (n + 2) - (n + 1 ) =2 - 2( vn + 2 - vn + 1 ) = Jn + 1 Jn + 1 Jn + 2 + Jn + 1

2 1 ;::: 0. Thus = Jn+T - Jn+2 n+1 n + 2 + Jn+T n+1 1 1 . 1 , 2, 3, 5, 8 , 1 3, 21 , 34, 55. (i)

= 2 +1•

vn+T .

1 But 2( Vn+l - 1 ) + Jn+T - 2( vn + 2 - 1 ) n+1 =

=

�.

nL+l r= l

Un +l Un Un -1 ( 7 ) n ( 7 ) n - l

u1

=

1 � =

+

�

4

+

4

1

J

r- ;::: 2( Jn + 2 - 1 ) .

yr

Groups, Rings and Fields

230

1.6 1 . N, 2. 3.

Z countable. Hence result . Identify a + bJ2 with (a, b) ; Z x Z is countable. A = (A U B) U (A \ B) is a disjoint union. Hence result.

4. {0, 1 } N uncountable. Hence NN uncountable. 5. Consider array x1 , x2 , . . . , x1 q

2.1 1 . (i) 1 , 2, 3, 4, 6, 8, 9, 1 2, 18, 24, 36, 72. (ii) 1, 2, 3, 4, 6, 7, 1 2, 14, 2 1 , 28 , 42, 84. (iii) 1 , 23, 29, 667. 2. If b divides -a then b = ( a )c = - ac for some c E 4 4 3. (i) z1 .3, (ii) 3.31 , (iii)5 2 .72 , (iv) 1 73 , (v) 2 .3 . 1 1 . -

Z, etc.

231

Hints to Solutions

2.2 1. ( i) 3, (ii) 12, (iii) 1 , (iv) 1 5. 2.3 1 . (i) q = 1 , r = 2. (ii) q = 3, r = 3. (iii) q = 6, r = 31 . (iv) 2513 = 46. 54 + 29, -2513 = 46( -54) - 29 = 46( -55) + (46 - 29) , q = -55, r = 46 - 29 = 1 7. (v) q = -71, r = 290. (vi) -52148 = ( -732)71 - 1 76 = ( -732 ) . 72 + (732 - 1 76) , q = 72, r = 732 - 1 76 = 556. 2. (i) (ii)

l x y l 2 = (xy) 2 = x 2 y2 = [l x i i Y i f Hence l xy l = l x i i Y I · l xl2 + I YI2 + 2l x i i YI = (l x l + I YI )2• l x + Y l 2 = (x + Y? = X 2 + Y2 + Hence l x + y l l x l + I Y I · 1 1 1 - 1 - 1 1 = 1 - 1 = o , 1 1 - (- 1 ) I = 1 2 1 = 2.

�

2xy �

2.4 1. a

= na', b = nb'(a', b' E Z). ax + by = na'x + nb'y = n(a'x + b'y) .

2. (i)

(ii) (iii)

(iv) (v) (vi) 3.

44 = 32.1 + 1 2, 32 = 12.2 + 8, 12 = 8 + 4, 8 = 4.2. G.C.D. 4. 4 = 1 2 - 8 = 1 2 - (32 - 12.2) = 12.3 - 32 = 3(44 - 32) - 32 = 3.44 4. 32. 150 = 1 05 + 45, 1 05 = 45 .2 + 15, 45 = 1 5 .3. G.C.D. 1 5. 1 5 = 1 05 - 45.2 = 105 - ( 1 50 - 105) 2 = 105.3 + 1 50( - 2) . 3718 = 1222.3 + 52, 1 222 = 52.23 + 26, 52 = 26. 2. G.C.D. 26. 26 = 1 222 - 52.23 = 1222 - (3718 - 1222.3).23 = 371 8( -23) + 1 222.70. 96 = 0. 764 + 96, 764 = 96.7 + 92, 96 = 92 + 4, 92 = 4. 23. G.C.D. 4. 4 = 96 - 92 = 96 - (764 - 96.7) = 96.8 - 764. G.C.D. 2. 2 = 6214. 1 595 - 7224. 1 372. G. C.D. 529. 529 = 1 52881 . 289 - 61 3640.72.

a2 - b2 = (a - b) (a + b), a3 - b3 = (a - b) (a2 + b2 + ab), a3 + b3 = (a + b) (a2 + b2 - ab). 3 divides 1 + 2 but does not divide 1 2 + 22 •

Groups, Rings and Fields

232

2.5 1 . Proof fur v'3 like proof fur ../2. m Suppose J6 = (m, n E N) where m, n have no common divisor i= 1 . n 2 2 m = 6n implies 2 divides m2 and so m. Let m = 2m' . Then 4m' 2 = m2 = 6n 2 and so 2m' 2 = 3n 2 . Thus 2 divides 3n2 and so 2 divides n, etc. 2. 3. 4.

q2 --5 E Q, false. ../2 + v'3 = q E Q implies J6 = 2 ±../2 irrational, ../2 + ( - .,/2) 0 rational. a, b, q E Z, q prime to b. Then there exist x, y E Z such that a = aqx + aby. =

1=

qx + by and

5. Pairs 3, 5 ; 5 , 7; 1 1 , 13; 1 7, 19; 29, 3 1 ; 41 , 43 ; 59, 61; 71 , 73 . 6. Apply sieve to numbers from 100 to 200. 7. 7r(10) 7r (70)

= 4, 7r(20) = 8, 7r(30) = 10, 7r(40) = 12 , = 19, 7r(80) = 22, 7r (90) = 24, 7r(l00) = 25.

7r(50)

= 1 5,

7r (60)

=

8 . Eleven ways.

3.1 1 . X + 2. 2. 3. 4.

x+l (x + 1) 2 • x2 + 1 .

3.2 1. (i) (ii) (iii) (iv) (v) 2. (i)

q(x) = 0, r(x) = x 3 + 3x2 + 1 . q (x) = x + 1, r(x) = - 1 . q (x) = � x + Fs , r(x) = � . q(x) = x 2 + x + 1 , r(x) = -2. q (x) = ! x2 + � , r(x) = - �. x4 + x3 + x + 1 = (x2 + x + 1)(x2 - 1) + (2x + 2) , + 1. x 2 + x + 1 = (2x + 2)

( �)

G.C.D. 1 . 1

=

(x 2 + x + 1 )

( � x3 - � x + ) - � (x4 + x3 + x + 1

1).

17,

Hints to Solutions

233

(ii) 2x3 + 10x 2 + 2x + 10 = 2(x 3 - 2x2 + x - 2) + (14x 2 + 14) , 1 xx3 - 2x 2 + x - 2 = (14x 2 + 1 4) 14 1 G.C.D. x 2 + 1 . x 2 + 1 = (2x3 + 10x 2 + 2x + 10) 14 1 - (x3 - 2x2 + x - 2 ) .

(

(iii)

�).

:4 - 4x3 + 2x - 4 = (x3 + 2 ) (x - 4) + 4 , x3 + 2 = 4 l � (x3 + 2) J. 1 1 G.C.D. 1 . 1 = 4 (x 4 - 4x3 + 2x - 4) - 4 (x - 4) (x 3 + 2) .

(iv) x3 + 5 x 2 + 7x + 2 = (x3 + 2x2 - 2x - 1 ) + (3x2 + 9x + 3) ,

(

)

1 1 x 3 + 2x 2 - 2x - 1 = (3x 2 + 9x + 3) 3 x - 3 G.C.D. x 2 + 3x + 1 . 1 1 x2 + 3x + 1 = 3 (x 3 + 5x 2 + 7x + 2) - 3 (x3 + 2x 2 - 2x - 1 ) .

3.3 1 . e, f identities.

e

=

e

·

f = f.

2. Check all axioms are satisfied. 3.

R is closed under addition and multiplication and the other axioms are satisfied.

4. Note that

R = Z2 • Check axioms.

5. Let x , y E Z. Then 2x + 2y = 2(x + y) , (2x ) (2y) = 2(2xy) . Thus closure of 2Z under addition and multiplication. Associativity of addition and multi­ plication , and also distributive laws , hold in Z and so in 2Z. Remaining axioms are clear. 2Z has no identity element . 6. (i)

If a + b = c + b then a = a + 0 = a + ( b + (- b ) ) = ( a + b ) + (- b ) = (c + b ) + (- b ) = c + ( b + ( - b ) ) = c + 0 = c.

(ii) - ( ab ) = - ( ab ) + 0 = - ( ab ) + O b = - ( ab ) + (a + ( - a) ) b = ( - ab ) + (a b + ( - a ) b ) ( - ( a b) + a b ) + ( -a ) b = 0 + ( - a ) b = ( - a) b . =

7. If A , B are 2 x 2 matrices over Q then so also are A + B , AB. Matrix addition and multiplication are associative etc.

Groups, Rings and Fields

234

8 . R1 n � -::j; 0 since 0 E R1 n � · Let x, y E R1 n � . Then x + y, -x, xy E R1 and x + y, -x, xy E �· Thus x + y, -x, xy E R1 n � which is therefore a subring. The intersection of any collection of subrings is a subring.

4.1 1. For all a, b, c E Z, a * b E Z and a * (b * c) = a * (cb) = cb(a) = c(ba) = ba * c = (a * b) * c, a * 1 = 1 a = a = a1 = 1 * a.

Uc,d o fa,b ) (x) = fc,d Ua,b (x)) = fc,d (a + bx) = c + d(a + bx) = c + ad + bdx = fc + ad, bd (x) . Circle-composition is asso ciative and /o, 1 is the identity for the

2.

monoid. 3.

Verify associativity,

0 + a = a + 0 = a.

4. There exists a' E S such that aa' = e and a" E S such that a' a" = e . Then ea = ea(e) = (ea) (a'a" ) = ((ea)a')a" = (e(aa' ))a" = (ee)a" = ea" = (aa' )a" = a(a'a" ) = ae = a. a" = ea" = (aa' )a" = a(a'a" ) = ae = a. 5. Since S is finite there exists N such that every power of a is equal to one of a, a2 , • • • , aN. Let p > 2N. Then there exists q, 1 � q � N , such that a! = a9 where p > 2N � 2q. AlSo b2 = (aP - 9 ) 2 = a2P - 29 = aPaP - 29 = a9 a!' - 29 = ap - q = b.

4.2 1 . No. 1 E N, -1

ft {0} U N.

2. x = ex = ( x - 1 x)x 3.

=

x - 1 ( xx)

=

x- 1 x = e.

(ab2 ) - 1 (c2 a - 1 r 1 (c2 b2 d) (ad) - 2 a = b - 2 a - 1 ac - 2 c2 b2 da 2 a - 2 a = d- 1 a - 1 • (abc) - 1 (ab) 2 d( d- 1 b- 1 ) 2 bdc = c- 1 b- 1 a- 1 ababda 1 b- 1 d- 1 b- 1 bdc = c- 1 ac.

aa = c "# b = de = (ab)c. -x (1 x) - 1 5 . (ac) (x) = a(c(x) ) = a(1 - x) = = = � = d( x) . 1-X X-1 -X

4. No. a(bc)

=

�

Thus ac = d, etc.

7.

6. Use de Moivre's Theorem. Use de Moivre's Theorem.

8. Let J, g be strictly monotonic. Then 0 � x 1 < x 2 � 1 implies 0 � g(xJ ) < g(x 2 ) � 1 and so 0 � ( f o g) (x 1 ) < ( f o g) (x 2 ) � 1 . Thu.<J f o g is strictly monotonic. Circle-composition is associative and t(x ) x gives identity. Inverse / - 1 of f is given by /- 1 ( x) = y if and only if f(y) = x. Prove r 1 is strictly monotonic! =

Hints to Sol utions

9·

( -ba ab ) (

-yx( xy) -) (-bx -( �

is associative.

G is Abelian.

ax - by ay a o E c, 1 -b

) _(

235

ay + bx E G. Matrix multiplication -by + ax b -1 a -b 1 = 2 a + u- b a E G. a

)

)

L2

y x-vt t-? x )(x t) t) = t -?x), t-?x-�( x (Jy-u1 - � Js -1 -�y)� (x-vJ1 t--u(� A t v ) ) J1 - � A t - �x) (x- wt t-?x) ( J1,-)x�-(Ju1 - �v)t , J1 ,-)�A

= �' s = � y1 -� y1 -� (Tu o Tv , = Tu (Tv (x, Tu ( Y, s )

(ii) L et

=

=

s

,

=

(1 +

+

where X �

(1 +

=

X

F!�� Jl-� + cr

,

X

c

Circle-composition is associative , T0 is the identity and (Tv) -1 = T- v·

4.3

1.

Let G

=

{e, a, a2 , a3 , a\ a5 } , a6 = e. Cayley table is: e a a2 a3 a4 as

e e a a2 a3 a4 as

a a a2 a3 a4 as e

From Cayley table { e, a } , { e, a2 ,

a2 a a3 a4 as e a a4 }

a3

a4

as

as e a a2

as e a a2 a3

e a a2 a3 a4

are the proper subgroups.

Groups, Rings and Fields

236

2. ALetn Ba, bn ECA. . n. B n C n . . .

Then

ab, a-1 E A, ab, a-1 E B, . . .

3. { e, a, b} is a normal subgroup. { e, c }, { e , d}, { e, !}

Thus

ab, a -1 E

are conjugate subgroups.

No other proper subgroups.

4. 5.

E G, a E A n B n c . . . Then x- 1 ax E A, x -1 ax E B, etc. Let u, v E a-1Ha. u = a-1 ha, v = a-1 ka(h, k E H ). uv = a -1 haa-1 ka = a-1 hka E a-1 Ha and u-1 = a-1 h-1 a E H. Thus a- 1 Ha is a subgroup. Hence n x-1 Hx is a subgroup. Let c = n x-1 Hx Then xEG xEG c E x -1 Hx for all x E G . Let y E G . y-1 cy E y- I x -1 Hxy = (xy) -1 H(xy) for all x E G. As x runs over the elements of G so does xy and So y -1 cy E x -1 Hx for all x E G. Thus y-1 cy E n x -1 Hx X

xeG

which is therefore normal.

6.

Let A , B be non-singular matrices. Then AB, A- 1 are non-singular as (AB) -1 = B-1 A -1 and ( A -1 ) -1 = A, etc. 1 a -I 1 a 1 b 1 a+b 1 -a = 0 1 ' 0 1 0 1 0 1 0 1 · Thus H is a subgroup which is obviously Abelian. Let c E Cc(A) , x E Nc(A) . We need to prove x-1cx E Cc(A) . Let a E A. Then xax-1 E A and so (x -1 cx) -1 a(x -1cx) = x -1 c-1 xax -1 cx = x -1 xax -1 x = a. Hence we have x-1cx E Cc(A) . Suppose NH is a subgroup. Then by closure HN � NH. Let x E NH. Then x- 1 E NH, x- 1 = nh (n E N, h E H ). Then x = h -1 n -1 E HN and So NH � HN. Thus HN = NH. Suppose now NH = HN. Let x, y E NH, x = nh, y = mk where m, n E N, h, k E H. Since hm E HN = NH, let hm = m'h' (m' E N, h' E H ). Then xy = nhmk = nm'h'k E NH and x-1 = h -1 n -1 E HN NH. Hence NH is

( )( ) (

7.

8.

)( ) ( =

)

=

a subgroup.

9. Each Hi contains I Hi I - 1 = I H I - 1 elements other than e. Thus H1 U H2 U . . . U Hn contains at most n( I H I - 1) elements other than e and so I H1 U H2 U . . . U Hn l :$ n(IH I - 1) + 1 . If G = H1 U H2 U . . . u Hn , then I G I :$ n( I H I - 1) + 1 :$ I G : H I (I H I - 1) + 1 = I G I - I G : H I + 1 which is impossible unless I G : H I = 1 and H = G.

Hints to S o lutio ns

237

4.4 1 . Let G = Nc(H)a 1 U Nc(H)a2 U . . . U Nc(H)an be a coset decomposition. Then the conjugate subgroups a11 Ha 1 , a21 H� , . . . , a;:;-1 Han are distinct and there are no other conjugate subgroups. 2.

x E G implies x - 1 E Hai (same i ) . Thus x E ai 1 H and so G = a1 1 H U a2- l H U . . . U an- l H . a;- l H = ai- l H 1' f and on1y 1·f a;- l = ai-l h- 1 (h E H ) , th at is a; = hai or Hai = Hai.

3. 1 2Z, 1 2Z + 1 , . . . , 12Z + 1 1 .

4.5 1. (g o f) (xy) 2. 3. 4.

= g( f (xy)) = g( f (x) f (y)) = g( f (x))g( f (y)) = (g o f) (x) (g o f) (y)

(x, y E G ) . aabb = f(a)f(b) = f(ab) = abab. Cancelling a and b gives ab = ba. f(x) = x -1 a -1 xa E Z(G ). f (x) f (y) = x -1 a -1 xay-1 a-1 ya = y-1 (x -1 a-1 xa) a-1ya = (xy)- 1 a- 1 (xy)a = f (xy) (x, y E G ). H/N = {Nh l h E H } . Let x, y E H. (Nx) (Ny) = Nxy, (Nx)- 1 = Nx- 1 . Thus H/N is a subgroup of GjN. Let W be a subgroup ofGjN. Let H be the subset of G given by {x E G I Nx E W} . Then prove that H is a subgroup of G, certainly HjN = W. x- 1 Hx H if and only if (Nx) -1 (H/ N) (Nx) = HjN. =

5. Proper subgroups are {e , a , b , c} , {e , a , d, f } , {e, a , g , h } and centre Z(G ) {e, a } . Classes are {e} , { a } , { b, c } , { d, f } , {e , g} . G = Z(G ) u Z(G )b u Z(G )du Z(G )g. Gj Z(G ) is a Klein four-group.

5.1 1. z2

Sum 0 I

z3

Sum 0 1 2

0 0 I

1 1 0

0 0 1 2

1 1 2 0

Product 0 0 0

I 0 I

Product 0

1 0 I 2

1

2 2 0 I

0 1 2

0

0 0 0

2

0 2 I

=

Groups, Rings and Fields

238 z4

2

Sum 0

0

I

1

2

3

I 2 3

I 2 3

2 3 0

3 0 I

0 I 2

=

0

3

I

Product 0 0 0 I 2 3

0 0 0

0

0

2

3

I 2 3

2 0 2

3 2 I

0

Z

X = 6, y 3, = 9. 3. x = a2 u 1m1 + a 1 u2m2 = a2 ( 1 - �m2 ) + a 1 �m2 = � - a2 u2m2 + a1 �m2 = � (mod �) . Similarly x a1 (mod mi } . 4. proper Ring axioms are easily verified. (ln, OE)(On, 1E) = (On, OE) implies that divisors of zero exist. 5. x(x - 1) = 0. Hence x = 0 or x - 1 = 0. 6. Verify assertions. 2.

=

5.2

1. x2 + x + 2 = (x - 3) 2 , x2 + 2x + 4 = (x - I) (x - 4) , x2 + x + 3 does not factorize, x - 1 = (x - 1 ) (x - 2) (x - 3) (x - 4) (x - 5 ) (x - 6). 2. 2.4 = I, = I, = I. 3. 3.16 = I, 23.45 = I, 24. 2 = I, 32.25 = I. 4. (i) �x + �y = ! } thus x + �y = �}x + 4y = 3 3x + 2y = 4 Solutions: X = y = 2; X = I, y = 3; X = 2, y = X = 3, y = X = 4, y = I. (ii) x + 3y = 2 } thus 33xx ++ 42yy == I2 } ' 3x + 2y = 2 Solutions: 3 . 2y = 3. 4 , giving y = 2, x = I. 5. 1 �x + 25y = 16 27x + 1 �y = 4 } } thus 8x + 21y = 1 8 27x + 5y = 22 ' Solutions: 7. 9y = 7 . 1 3 , giving y = 29 , x = 23. 6. ax + y = I } t us ax + y = -I } . x + f3y = {3 ax + y = 1 Solutions: x = y = I; x = I, y = {3; x = a, y = a ; x = {3, y = 6

-

-

-

-

-

-

-

6.6

3.5

4;

0,

0;

h

0,

0.

239

Hints to Solutions 7.

u, v E U(R) , (uv) - 1 = v-1u-1 , so uv E U(R) etc.

8. F \ {0} .

a, b, c E Z, (a + bv'3) + (c + dv'3) = (a + c) + (b + d) v'3 E S, (a + bv'3) (c + dv'3) = ( ac + 3bd) + - (a + bv'3) = (-a) + ( -b) v'3 E S, (ad + be ) v'3 E S. Now S � lR and so S is a subring of JR. S is an integral domain but is not a field. 10. Certainly S is an integral domain. But 0 f. a + bv'5 E S implies 1 = a - bv'5 E S and so S IS. a field. a + bv�o a + 5b 1 1 . S is a field. Prove! 12 . Induction: (a + b) P = ((a + b) P ) P = (a P + bP ) P = (a P ) P + (b P ) P = a P + b p . 9. For all

2

2

n

13.

n+l

n

n+1

n+ 1

(t.·r� t.·t( ; )

Write elements

z _ w

as

n

n

where z,

w

n

are complex conjugates of z ,

Hence prove result.

5.3

1 . a + bi is a unit if and only if a2 + b2 = 1 . Thus units are ± 1 , ± i. 2. (i) 1 + 13i = (- 1 + 2 . ) + - 2 + 1 . 1 5 51 4 - 3i r = (1 + 13i) - (4 - 3i) (- 1 + 2i) = -1 + 2i. q = - 1 + 2i , (ii) 5 + 1 5i = 1 + 2I" . 7+T r q = 1 + 2i , 0. (iii) 5 + 6� = (-1 + 2i) + � + _!_ i . 1 - 31 13 13 q = - 1 + 2i, r = (5 + 6i) - (2 - 3i) ( -1 + 2i) = 1 - i. 3. For a , "(, 8 E Z,

(

=

(

·

)

)

Now follow the proof for the Gaussian integers.

w.

Groups, Rings and Fields

240

4.

=

w2 = w = -1 - w, w'W = 1 . D is a ring since (a + f3w) + (-y + 6w) (a + -y) + ({3 + 6)w, (a + {3w) (-y + 6w) = (a-y - {36) + ( -{36 + fYy + a6)w and .

D 5; C

�::: = (m + c) + (n + ry)w (m, n E Z, l e i � � . 1 77 1 � D· r

= (a + {3w) - (-y + 6w) (m + nw) = (-y + 6w)(c + ryw) . Now prove I c + rywl 2 = c2 + 772 - cry � �

and follow proof for Gaussian

integers.

2. The intersection of a collection of left ideals is a left ideal. 3.

00

U Li . For some N, a1 , � E LN. Thus immediately we have i=I a1 + a2 , -a� , xa1 E LN. Hence a1 + a2 , -at . xa1 E U L; which is therefore

x E R. a1 , a2 E

oo

i=l

a left ideal.

4. 0 E A since xO = 0 0 + 0 = 0, x( -a) = right ideal.

(x E X ). y E R, a1 , � E A. x(a 1 + a2 ) = xa 1 + xa2 = -(xai ) = 0, x(a1y) = (xai )y = Oy = 0. Hence A is a

la + Oa, a is in subset. Now prove subset is a left ideal. 6. M = {x E Ri f (x) E L}. y E R, u, v E M. f(u + v) = f(u) + f(v) E L, f(-u) = -f(u) E L, f (yu) f(y) f (u) E L. Thus we have u + v, -u, yu E M. Hence M is a left ideal. 7. f (L) is certainly a subring of S. Let a E f (L), x E S. Then a = f (b) (b E L) , x = f(y) (y E R). xa f(y)f(b) = f(yb) E f(L) . Thus f (L) is a left ideal of S. 8. x, y E S, a, b E I. (x + a) + (y + b) = (x + y) + (y + b) E S + I, -(x + a) = (-x) + (-a) E S + I, (x + a) (y + b) = xy + (ay + xb + ab) E S + I ( l is an ideal ) . Thus S + I is a subring. Alcro I n S is a subring of S. If x E S, a E I n S, then xa E I (I left ideal ) and xa E S (S subring ) . Thus xa E I n S which is a left ideal of S. 9. R, S, T are additive and multiplicative semigroups. Hence result. 5. Since a =

=

=

Hints to Solutions

241

10. ( a + i b) + (c + id) = (a + c) + i(b + d) -+ c - �b b d) (a + ib) (c + id) = (ac - bd) + i(bc + ad) --+ -b � d- c �b

( � : ::�) ( :) + ( �d �)

( : : ::� :�) ( :) ( �d :)

.

As mapping is bij ective result follows.

5.5 1 . M maximal implies R/ M is a field and so R/ M is an integral domain. Hence M is prime. {0} is prime , but not maximal, in Z. 2. 4 + 2i = (1 - 3i)i + (1 + i) , 1 - 3i = (1 + i) ( -1 (4 + 2i) 1 + (1 - 3i) (-i) = 1 + i (G.C.D.).

- 2i ) .

Hence it follows that

3. Certainly Da1 + Da2 + . . . + Dan = Dd for some d. Then x1 a1 +xn an = d for some x1 . x 2 , , xn E D . Prove now d is G.C.D.

+ x 2 a2 + . . .

• • •

5.6 1 . Three polynomials are irreducible by Criterion for p = 5, 7, 13 respectively. 2.

19 + 24x + 9x2 + x 3 = 3 + 9y + 6y2 + y3 which is irreducible by Criterion for

p

3.

= 3.

x 3 + 9 not irreducible in Q[x] implies that x 3 + 9 ha.s a linear factor x + a (a E Q) . Then a3 + 9 = 0 (a E Q) which is impossible.

2. Direct verification. 3. (1 (6

2) (1 4 ) (6

6) ( 1 7) ( 1 8) (6 5) (6

5) (1 3) odd , (1 3 ) ( 1 2 ) (6 1 ) (6 7) even.

4)(1

2) odd ,

4. ( 1 ) , (1 2 ) (3 4) , (1 3 ) (2 4) , (1 4 ) (2 3), (1 2 3) , (1 3 2) , (1 4 2), (1 2 4) , (2 4 3) , (2 3 4) , (1 4 3) , (1 3 4) . 5. Skew-symmetric.

Groups, Rings and Fields

242

6. Ker f = 7.

8. 9.

{a E G la.x = X for all X E G } =

n

xeX

Stabc(x) .

G = a 1 Stabc (x) U a2 Stabc (x) U . . . U CLnStabc(x ) . Prove orbit of x consists precisely of a .x, a2 .x, . . . , an .x and that a;.x = ai .x if and only if 1 aj 1 a; E Stabc(x) . a, b E G. (ab) .Hi = (ab)H; (ab) -1 = abH;b-1a-1 = a.(b.H;). Stabc(Hi) = Nc(Hi) · Hence n = I G : Nc(H ) I . e -+ (1 ), a -+ (1 2 3), b -+ (1 3 2), c -+ (1 2) , d -+ (1 3), f -+ (2 3).

6.2

1. b = a - \ a3 = e, b2 = e implies a = b = e, I G I = 1 . 2. From aba? = b, b- 1 ab = a- 2 = a2 • Hence b- 1 a2 b = a4 = e and so a2 = e. Thus ab = b and a = e. G = (b l b2 = e). 3. The elements of G are of the form an or ban (n = 0, 1, . . . , 7) . Thus I G I = 1 6 . a 4 h as order 2 but (ban ) 2 = ban ban = b2 b-1an ban = b2 a - n an = b2 i= e (n i= 0) . Hence a4 generates only subgroup of order 2. 4. G is the dihedral group D3 . 5. Label vertices consecutively as 1 , 2, 3, 4. Group of transformations is { (1 ) , (1 4) ( 2 3) , (1 2 ) ( 3 4 ) , (1 3) (2 4) }. 6. As in text for Dn . 6.3

1. AB is normal. Hence ABC = (AB)C is normal. 2. G = H x K. a, b E G, a = xy, b = zt (x, z E H; y, t E K). ab = (xz) (yt), ba = (zx) (ty). Hence result. 3. Obvious as Hj(H n K) n Kj(H n K) = { H n K}. 4. No. G = (a, b l a + b = b + a, 2a = 2b = 0}, A = (a}, B = (b), C = (c), where c = a + b. Then G = A + B + C, A n B = A n C = B n C = { 0 } .

243

Hints to Solutions

6.4

1 . a, b E M implies rna = 0, nb = 0 (rn, n E N) . rnn(a + b) = n(rna) + rn(nb) = 0 + 0 = 0, rn( -n) = - (rna) 0, thus M is a subgroup. Suppose x E A, r E N is such that r (x + M) M. Then rx + M = M and so rx E M. Then for some s E N, s ( rx ) = 0 and so ( sr ) x 0 and x E M. 2. na + nb = n(a + b) (a E A) , - (na) = ( -n)a. Hence nA is a subgroup. In solutions 3-5 let Cn be cyclic of order n. 3. 20 = 22 . 5 . c2 X c2 X Cs , c4 X Cs . 4. 12 = 23 .3 2 . c2 x c2 x c2 x c3 x C3 , c4 x c2 x c3 x C3 , Cs x C3 x C3 , =

x

=

=

C2 x C9 , C4 x c2 x Cg , Cs x Cg . 2 5. 2250 = 2.3 . 5 3 . c2 X c3 X c3 X Cs X Cs X Cs , c2 X Cg X Cs X Cs X Cs , c2 X c3 X c3 X Cs X Cs X C2s , c2 X Cg X Cs X c25 • c2 X c3 X c3 X cl 25 • c2 x c9 x C1 2s · c2

6.5

1.

2.

C2

x

Z(G ) i= { e } . If Z(G ) i� not a subgroup of H then H C HZ( G ) � Nc (H ) . If Z (G ) � H then argue by induction on I G I . Result is true for G/Z(G ) . Then HjZ(G ) is not the normalizer of H/Z(G ) in GjZ(G ) from which H is not the normalizer of H in G. Deduction is clear. r G I = 4 5 32 .5. Let rn be the number of Sylow 3-subgroups. Then we have rn = 1 + 3r and 1 + 3r divides 3 2 . 5 . Hence r = 0, rn = 1 . Let P be the unique Sylow 3-subgroup. Then P has order 9 and so is Abelian. Let n be the number of Sylow 5-subgroups. Then n = 1 + 3 s and 1 + 3 s divides 32 . 5 . Hence s = 0, n = 1 . Let Q be the unique Sylow 5-subgroup. Then Q has order 3 and so is Centre

=

cyclic. Since

G = P X G result follows. I G I = 207 = 3 2 . 23. Let rn, n be the numbers of Sylow 3-subgroups and 23subgroups respectively. rn = 1 + 3r, n = 1 + 23 s and rn and n divide 32 .23. Hence rn = 1 , n = 1 . G is the direct product of its (Abelian ) Sylow subgroups

of orders 9 and 23 and so is Abelian.

3. P is a Sylow �subgroup of G and of PN. Let l PN I = I P irn, I G I = I P irnn where rn, n are integers not divisible by p. But PN / N is isomorphic to P/(P n N) and so

I PN I INI

I P I g1Vlng . . N = I P n N I I PN I = I P n N I I P i rn P n N rn. =I I I l I PI IPn Nl I PI

244

Groups, Rings and Fields

Thus P n N is a Sylow p-subgroup of N. Hence a Sylow p-subgroup of Gf N has order I P : P n N l = l PN : Nl. Thus PN/N is a Sylow p-subgroup of

GfN.

4. If p = q the group is Abelian and result is true. If p > q let n be the number of Sylow p-subgroups. Then n = 1 + rp and n divides pq. Hence r = 0, n = 1 and the Sylow p-subgroup is unique. 5. If 1 + 5k divides 60 then 1 + 5k is 1 or 6. 6. 351 = 3 3 . 1 3. Let n be the number of Sylow 13-subgroups. Then we have n = 1 + 13k and 1 + 13k divides 3 3 .13. Hence 1 + 13k = 1 or 27. If 1 + 13k = 1 there is a unique Sylow 13-subgroup. If 1 + 1 3k = 27 the group contains 27 Sylow 13-subgroups. Then the number of elements in Sylow 1 3subgroups is given by 27(13 - 1 ) + 1 = 325. Thus there are 351 - 325 = 26 remaining elements. But a Sylow 3-subgroup h88 27 elements including the identity element. Thus the remaining elements must be from a Sylow 3subgroup which is unique. Hence there is a normal Sylow 1 3-subgroup or a normal Sylow 3-subgroup.

Suggestions for Further Study

1. Beginning Texts R.A . Dean , Elements of A bstract A_lgebra (Wiley, 1967) . J.B. Fraleigh, A First Course in A bstract A lge bra (Addison-Wesley, 1 989) . J.A. Galli an , Cont emporary A bstract Algebra (D.C. Heath, 1 994) .

2 . Advanced Texts P.M. Cohn, Algebra, vols. 1-3 (Wiley, 1 991 ) - has an extensive bibliography. N. Jacobson , Basic A lgebra, vols. I and II (W.H. Freeman, 1 985) . B.L. van der Waerden , Modem A lgebra, vols. I and II (F. Ungar , 1 948) - the classic text and still worth a look.

3. Hic;torical Texts V.J. Katz, A History of Mathematics (HarperCollins, 1 993) . B.L. van der Waerden , A History of Algebra (Springer-Verlag, 1 985).

245

Index

Abel, N . H . 93 Abelian 93, 107 Abelian group 93, 107 absolute value 54 act 198, 201 action 1 98 addition 82 , 94 algorithm 50 Al-Khwarizmi 50 alternating group 2 0 1 arithmetic modulo n 145 Arithmetica 168 associate 1 7 7 associativity 24, 82 , 94, 1 0 0 Associativity a n d Index Law 9 5 axioms 82 Axioms of Addition 82 Axioms of Distributivity 83 Axioms of Multiplication 83 Bertrand, J . 69 bijective 20 binary 82 BODMAS 84 cancellation 100, 1 0 1 cardinality 2 Cartesian product 7 Cauchy, A.-L. 2 1 9 Cayley table 102 Cayley, A. 93, 203 central 1 1 3 centralizer 1 19, 1 2 6 centre 1 1 3 characteristic 155 Characterization of a Field 1 5 1

Chebyshev, P.L. 69 China 1 49 Chinese Remainder Theorem 149 circle-composition 2 1 , 24 closure 82, 94, 100 codomain 18 coefficient 73 common divisor 50, 1 8 1 commutative 8 8 , 107 commute 88, 107 complement 6 complex numbers 1 9 composite 49 congruence 145 congruent 146 conjugacy 1 1 3 conjugacy class 1 13, 1 32 conjugate 1 1 2 , 120 constant polynomial 73 content 186 coprime 62 corps 151 coset 1 2 8 coset decomposition 129 countable 41 cubic 73 cycle 1 95 cyclic 1 1 1 D e Moivre, A . 1 1 1 D e Morgan Laws 1 2 D e Morgan, A . 1 2 Dedekind, R 7 1 , 1 5 1 , 168 degree 73 Descartes, R 7

246

Index dihedral group 1 1 8, 209 Diophantus 168 direct product 2 1 0 direct product (external) 2 1 0 direct product (internal) 2 1 1 direct sum 2 1 2 direct sum (external) 2 1 2 direct sum (internal) 2 1 2 disj oint 5, 1 96 disj oint union 5 Distributive Laws 1 2 divides 48, 7 4 Division Algorithm 52 , 54, 76 divisor 48 , 7 4, 75, 1 77 divisor of zero 88 domain 1 8 Dyck, W. von 93 Eisenstein, F.G. M. 189 Eisenstein's Criterion 189 element 1 , 3 elementary p-group 2 1 1 empty set 2 Epimenides of Crete 45 epimorphism 1 39, 1 74 equal 4, 73 equivalence class 30 equivalence relation 28, 58 Eratosthenes 68 Euclid 56 Euclidean Algorithm 56 , 79 Euclidean domain 163 even 198 factor-group 1 39 factor-ring 17 4 Fermat, P. 1 68 Fermat's Last Theorem 1 68 Fibonacci 40 field 151 finite characteristic 154 finite group 1 02 finite index 1 2 9 finite order 1 0 2 , 1 1 1 finite set 2 First Isomorphism Theorem 1 4 1 , 1 75 fix 192 Fraenkel , A.H. 7 1 function 1 8 Fundamental Theorem o f Arithmetic 66 Galilei , G. 1 1 0 Galois, E. 9 3 Gauss, K.F. 6 9 , 166 Gaussian integer 1 66 Gauss's Lemma 187 general linear group 124 generate 1 1 1 generator 1 1 1 generators 206 Goldbach, C . 70, 84

247 greatest common divisor 5 1 , 75, 8 1 group 99 Hadamard, J. 70 Haimes, P.R. 150 Hamilton, W. R. 163 Hasse diagrams 143 Hasse , H . 143 Hilbert , D. 71 Hindu-Arabic numerals 40 homomorphism 1 34, 1 7 1 ideal 1 68 identity 87, 95, 100 identity element 87, 95 identity permutation 192 image 18 indeterminate 73 index 129 Index Law for Groups 1 06 induce 202 infinite cardinality 2 infinite characteristic 154 infinite dihedral group 207 infinite group 1 02 infinite index 129 infinite order 102, 1 1 1 infinite set 2 injective 20 integers 19 integral domain 82, 88 International Standard Book Number 1 50 intersection 5 inverse 100, 150 inverse of addition 84 invertible 1 50 irrational 19 irreducible 1 78 , 1 79 , 1 86 isomorphism 139, 1 74 kernel 136, 172 Klein four-group 105 Klein, F. 105 Kerper, 1 5 1 Kronecker, L. 4 7 , 93 Kummer, E.E. 168 Lagrange, J .-L. 1 30 Lagrange's Theorem 130 left coset 1 28 left ideal 168 Leonardo of Pisa 40 Liber Abbaci 40 linear 73 linear fractional transformations 206 Lorentz, H.A. 1 15 map 18 mapping 18 matrix 42, 91 maximal l 78 modular 145

248 modulus 54 monic 73 monoid 95 monomorphism 139, 1 7 4 move 192 multiplication 82, 94 Napoleon 41 natural numbers 1 9 non-Abelian 1 07 non-commutative 107 non-singular 124 normal 120 normalizer 1 2 2 , 126 not congruent 146 not equal 4 null set 2 odd 1 98 one-one 20 one-one and onto 20 onto 20 orbit 202 order 1 1 1 , 1 1 2 Orwell, G . 4 1 partition 3 2 permutation 1 92 permutation group 192 p-group 2 1 1 P lato 63 polynomial 72, 73 prime 49, 178, 1 79, 186 prime characteristic 1 55 prime number 49 primitive 186 principal ideal 1 8 1 principal ideal domain 1 8 1 Principle of Induction 3 5 Principle of Well-ordering 3 4 product 82 proper 4, 1 1 6 proper divisor o f zero 88 property 4 p-subgroup 2 16 quadratic 73 quaternion group 144 quaternions 163 quotient field 159, 161 range 18 rational functions 1 62 rational numbers 19 real numbers 1 9 reflexive 28 related 27 relations 2 06 relative complement 6 Remainder Theorem 77

I ndex right coset 128 right ideal 1 68 ring 82 Ruffini, P. 93 Russell, B . 45 Second Isomorphism Theorem 142, 175 self-conjugate 113 • semigroup 94 set 1 sieve 68 simple 143 skew-symmetric 198 St. Paul's Epistle 45 stabilizer 202 Steinitz, E. 1 5 1 strictly positive integers 1 9 subfield 1 56 Subfield Criterion 156 subgroup 1 1 6 Subgroup Criterion 1 1 6 subring 90 Subring Criterion 90 subset 3 sum 82 surjective 2 0 Sylow subgroup 2 2 0 Sylow, P.L. 2 19 , 2 2 1 symbols 1 92 symmetric 2 8 , 1 98 symmetric group 1 92 The Elements 56, 63, 66, 67 Theaetetus 63 Theodorus 63 transitive 28 transposition 195 trivial divisors 48, 74 two-sided ideal 168 uncountable 41 union 5 unique factorization domain 1 80 Unique Solution of Equation 1 02 unity 87 universal set 4 Valllle-Poussin, C . J . de Ia 70 Venn diagrams 8 Venn, J . 8 Waerden , B.L. van der 150 Weber, H. 93, 1 5 1 Weyl, H. 4 7 Wiles, A. 1 6 8 Wussing, H. 9 3 zero 83 zero characteristic 154 zero ideal 168 zero polynomia 73