Algebra: Volume I

(an) = a,. + 1. Since
Fmite and Countable (Denumerable) Sets

9

subscripts so that every natural number is used as a subscript exactly once. Finite sets and denumerably infinite sets are both called denumerable or

countable. Exercises 1.5. Prove that the number of elements in a union of two mutually exclusive finite sets is equal to the sum of the numbers of the individual sets. (Mathematical inductiop. by means of the recursion formulae (1.1), (1.2), Section 1.3.) 1.6. Prove that the number of elements in a union of T sets any two of which are mutually exclusive and each of which contains s elements is equal to rs. (Mathematical induction by means of the recursion formulae (1.6), (1.7), Section 1.3.) 1.7. Prove that any subset of the number sequence is countable, and hence derive that a set is countable if and only if its elements can be labeled with numbers so that distinct elements will have distinct labels. AN EXAMPLE OF A NONDENUMERABLE (UNCOUNTABLE) SET The set of all denumerably infinite sequ~nces of natural numbers is uncountable.

It is readily seen that it is not finite. If it were denumerably infinite, each sequence would have a subscript, and to each subscript i belongs a sequence which we may denote by Now let us write the following sequence:

This sequence would likewise have to have a subscript, for example, the subscript j. Thus we would have and in particular which is a contradiction.

Exercises 1.8. Prove that the set of all integers ,(positive, negative, and zero) is denumerably infinite, and also that the set of the even numbers is denumerabIy infinite. 1.9. Prove that the cardinality of a denumerably infinite set does not change if a finite number or a denumerably infinite number of new elements is added.

10

NUMBERS AND SETS

Theorem: The union of a countable set of countable sets is itself countable. Proof: Let the countable sets be denoted byID1 1 , rol 2 , ••• ,and let the elements of 9)11 be mil' mi2' • •• • There are only a finite number of elements mile with i + k = 2 and likewise a finite number of elements with i + k = 3, and so on. By first labeling the elements for which i + k = 2 (for instance, in the order of increasing values of i) and then (continuing in numerical order) those with i+k = 3 and so on, each element mile will eventually have a subscript, and distinct elements will have distinct subscripts. This proves the above assertion.

1.5 P ARTmONS The equality sign satisfies the following conditions: a

a =.b

if a

=b

= a;

implies

b

= a;

= c, then a = c. = b is reflexive, symmetric, and transit've

and b

We may say instead: The relation a If, among the elements of any set, a relation a""b is defined (so that for each pair of elements a, b it is known whether or not a",b), and if this relation satisfies the same conditions, 1.

a~Q;

2. a"",b implies b"-JQ; 3. If a,....,.",b and b"",c, then af'tlc; then the relation a"",b is called an equivalence relation. Example: In the set of integers, consider two numbers equivalent if their difference is divisible by two. The axioms are obviously satisfied. Now, whenever an equivalence relation is given, we may put all the elements equivalent to an arbitrary element a into one class $lao Then all elements of a class are equivalent to each other; for according to conditions 2 and 3 it follows from a""b and a""c that b~c, and all elements equivalent to an element of the class are in the same class, since it follows from a~b and b~c that a~c. Thus a class is determined by anyone of its elements. If, instead of from a, we start from any element b of the same class, we arrive at the same class: .Rb = .Ra • Accordingly, we may choose any b as a representative of the class. However, if we proceed from an element b not belonging to the same class (that is, not equivalent to a), the .Ra and.R b cannot have a common element; for from cr".Ia and cr".lb it would follow that ar--lb, and hence b E $lao Thus the classes Sta and St b are mutu311y exclusive in this case. The classes cover the given set entirely, since every element a lies in a class, namely in 5\al Thus the set is divided into classes all mutually exclusive. In our

Partitions

11

last example, these classes are the class of even integers and the class of odd integers. We have seen that.Ra = -Rb if and only if a~b. By introducing classes instead of elements we may replace the equivalence relation Ql"Jb by an equality relation

R" = 5th -

If, conversely, a given set IDl is partitioned into mutually exclusive classes, we may define ar-wb if Q and b belong to the same class. Obviously, the relation a,-.,.,b satisfies conditions 1, 2, and 3.

Chapter 2 GROUPS

Explanation of fundamental concepts of group theory which are essential for the entire book, such as group, subgroup, isomorphism, homomorphism, normal divisor, and factor group.

2.1 THE CONCEPT OF A GROUP A nonempty set 03 of any sort of elements (such as numbers, mappings, transformations) is said to be a group if the following four postulates are fulfilled. Definition:

1. A rule of combination is given which associates with every pair of elements a, b of (fi a third element of the same' set, which most frequently is called a product of a and b and which is denoted by ab or a-b (the product may depend on the order in which the factors are arranged; ab mayor may not be equal to 00)_ 2. The associative law: If a, b, c are any elements of (f), then

ab·c = a-bc. 3. There exists (at least) one element e in 03, called the (left) identity, so that ea = a. for every element a of (fj. 4. If a is an element of (fj, there exists (at least) one element a-I in (fj, called the (left) inverse of a, so that a- 1 a = e.

A group is called Abelian if ab is always equal to ba (commutative law). Example: If the elements of the set are numbers, and if the rule of combination is ordinary multiplication, then the zero, for which there is no inverse, has to be excluded. All rational numbers =1=0 form a group (the identity is the number 1); the numbers 1 and -1, or the number 1 all by itself form groups_

ADDrnvE GROUPS The group concept does not depend on the notation for the group operation a-b: the operation may well be addition, for examp1e, the ordinary addition of 12

The Concept of a Group

13

integers or vector addition. In postulates 1 through 4 we need only replace the product a·b by the sum a+b. The group (fj is then called an additive group or a module. In this case the identity element e will be the zero element 0 with the property for all a in (», O+a= a and in place of the inverse a- 1 there is the element -a with the property

-a+a = O. Addition is usually assumed to be commutative:

a+b

=

•

b+a.

For brevity, a-b is written in place of a+( -b). It thus follows that

(a-b)+b = a+( -b+b) = a+O = a. EXIUllpIe: The integers form a module, as do the even integers.

PERMUI'ADONS A permutation of a set !R is a one-to-one mapping of the set IDl onto itself, that is, a correspondence s in which to each element a of ro1 there is an image s(a), and each element of m is the image of exactly one a. We also write sa for s(a). In the case of infinite sets, IDl permutations are sometimes called transformations, but the word transformation is also used in a wider sense as a synonym for mapping. If the set 9Jl is finite, and if its elements are labeled with subscripts 1, 2, ... , n, then any permutation may be described completely by a symbol in which, below every SUbscript k, the subscript s(k) of the image is written. For example, the symbol

1 2 3 4) s= ( 2431 is that permutation on the digits 1, 2, 3, 4 which carries 1 into 2, 2 into 4, 3 into 3, and 4 into 1. The product st of two permutations s and t is defined as the permutation resulting from first applying t and then applying s to the images1, that is,

st(a) == s(t(a»; for example, if

1 2 3 4) s= ( 2431

and t

I 2 3 4)

== ( 2 1 4 3 '

then

1 2 3 4) st= ( 4213· 1The order is

a matter of convention. By st older authors sometimes mean: first s and then t.

14

GROUPS

Similarly

ts

1 2 3 4)

= (I

3 4 2 ·

The associative law (rs)t = rest)

can be proved for mappings in general in the following manner. Applying both sides to an arbitrary object a, we obtain (rs)t{a)

= (rs)(t(a»

= r(s(t(a»)

r(st)(a)

=

r(st(a»

= r(s(t(a»),

and thus the same result is obtained in either case. The identity or identity permutation is the mapping 1 which maps each object onto itself: /(a) = a.

The identity obviously has the characteristic property of the identity element of a group: Is = s for every transformation s. We sometimes write 1 instead of I. The inverse of a permutation s is that permutation which maps sea) onto a and thus cancels the effect of s. Denoting this permutation by S-I, it follows that for every object a

and hence

Exercises

2.1. A nonempty set OJ of transformations of a set W1 is a group if it contains

2.2.

2.3.

(a) the product of any two transformations and (b) the inverse of each transformation. The rotations of a plane about a fixed point P form an Abelian group. If the reflections across a111ines through P are also included, a non-Abelian group is obtained. Prove that the elements e, a with the composition law

ee = e,

ea = a,

ae = a,

aa

=

e

form a (Abelian) group. Remark: The composition scheme of a group can be represented by a "group table," a table with double entry in which for every two elements the product is entered. For example, the table for the group above is

Ie

a

: I: :.

The Concept of a Group

15

Exercise 2.4.

Form the group table for the group of permutations of three numbers.

It follows from what has just been proved that all postulates 1-4 are fulfilled for all permutations on a set Wl. Therefore all these permutations form a group. For a finite set IDl with n elements the group of its permutations is called the symmetric group2 6,.. Let us now return to the general theory of groups. For ab-c or a-bc we shall write briefly: abc . From postulates 3 and 4 follows

if we multiply on the left by an inverse element of a-I, we have eaa- 1

=e

or

aa- 1 = e; thus, every left inverse is also a right inverse. At the same time we see that the inverse of a -1 is a again. Furthermore, we infer: ae

= aa -1a = ea = a;

thus the left identity is also a right identity. Now the possibility of a right.. and left-hand division follows also. 5. The equation ax :::: b as well as the equation ya where a and b are arbitrary elements of <». These solutions are x = a- 1 b and y

= ba- 1,

= b have solutions in (fj,

since

= (aa-t)b = eb = b (ba-1)a = b(a- 1 a) = be = b. a(a- 1b)

The uniqueness of division can be proved just as easily.

6. ax = ax' and likewise xa = x'a imply x = x'. For ax = ax' yields x = x' when both members are multiplied by a- 1 from the left. The second part of the above assertion may be proved in exactly the same manner. 2The reason for this name is that the functions of Xl, ••• , x,., which remain invariant under all permutations of the group, are the "symmetric functions. n

16

GROUPS

In particular, we may infer the uniqueness of the identity (as the solution of the equation xa = a) and the uniqueness of the inverse (as the solution of the equation xa = e). The (only) identity is often denoted by 1. The possibility of division, 5, can replace postulates 3 and 4. In fact, let us assume that 1,2, and 5 hold, and let us first prove (3). We choose an element c, and bye we denote a solution of the equation xc = c. Then

ec

= c.

For any a we now solve the equation

cx = a. Then

ea=ecx=cx=o, which proves (3). Postulate 4, on the other hand, follows directly from the solvability of xa = e. Thus we may always employ 1, 2, 5 as equivalent group postulates instead of postulates 1, 2, 3, 4. If (fi is a finite set, postulate 5 may be replaced by 6. Thus we need not even assume the possibility of division, but merely its uniqueness (besides postulates 1 and 2). Proof: Let a be any element. With e,very element x we associate the element ax. According to 6, this pairing constitutes a one-to-one correspondence; that is, the set ffi is mapped in a one-to-one manner on a subset, namely the set of all products ax. However, since (fj is a finite set by hypothesis, it cannot be mapped on a proper subset by a one-to-one correspondence. Therefore the totality of the elements ax has to be identical with <»; that is, each element b can be written in the form b = ax as asserted in S. The solvability of b == xa is proved in the same manner; hence 5 follows from 6. The number of elements of a finite group is said to be the order of the group. FURTHER RULES OF OPERATION For the inverse of a product the following rule holds:

(00)-1 = b- 1a- 1 since

COMPOSITE PRODUCTS (SUMS); POWERS In the same fashion as we denoted ab· c briefly by abc, we shall define the composite products of several factors

n• n• Qy

,,=1

=

1

Qy

=

ala2 · · • all-

17

The Concept of a Group

If at, ... , aN are given, the recursive definition (for n < N) is 1

TIa,,= at 1

3

4

TIa"

TI

In particular, is our old al a 2a 3, and = ala2a3a4 = (a 1a2Q J)a4, and so on. 1 1 We shall now prove the following rule solely by means of the associative law: m,.

TIa,,· TIa

1t=1

w=1

m+n

=y=1 nay.

m+ v

(2.1)

In words this may be expressed as follows. The product of two composite products is equal to the composite product of all their factors in the same serial order. For example,

(ab) (ctl)

= abed

is a special case of (2.1). For n = 1, formula (2.1) is clear (by definition of the symbol). Once it has been proved for a value n, we have for the next higher value n+ 1:

n

=

Qa,.

111+11 (

.+ .. + 1

)

a.+ II +l

- TI

aye

I

This proves (2.1). ..

Note:

TII a",+

m+n v

is also written in the form nay. Occasionally, if it is

vement, we may write

0

TI a

y

COD-

_+1

=

e.

1·

A product of n identical factors is called a power:

a-

" =TIa 1

(in particular at

= a, a2 =

aa,

and so on). 3The symbol v, denoting the variable index, may of course be replaced by any other symbol without changing the meaning of the product.

18

GROUPS

From the theorem just proved it follows that

(/'·a'" = c/'+"'.

(2.2)

(a"')" = am".

(2.3)

Furthermore, We leave the proof (by mathematical induction) to the reader. The rules (2.1), (2.2), (2.3), proved so far, required but the associative law for their proof, and therefore they will be applied in the following sections to all kinds of domains in which products are defined and where the associative law holds (such as in the domain of the natural numbers), even though these domains may not be groups. Hthe mUltiplication is commutative as well (Abelian groups), it can be proved that the value of a composite product is independent of the order in which the factors are arranged, or more precisely: Ifcp is a one-to-one mapping olthe segment (I, n) of the natural numbers upon itself, then

n,.

a,,(v)

=

1'=1

n" ave 1

Proof: For n = 1 the assertion is obvious; therefore, assume it to be correct for n -1. There exists a k which is mapped into n: cp(k) = n. Then

n "

,J1 I

1

n

a,,(v)

=

1

n

n-t

k-I

atp(y)· a,,(k)·

1

n na~(Ie+

k-1

a,,(Ie+ v) =

1

n-k

a,,(v) ·

1

v)· a,,(k)-

4

The product in parentheses contains just the factors a1, •• • ,0,.-1 in some order.

nay. We thus obtain

n-l

According to the induction hypothesis, it is equal to

1

n n

1

n-1

a,,(v)

=

n

nay·a" 1

= nay. 1

From the rule just proved it follows that for Abelian groups a notation such as

n n

aile,

l~'
or

all,

(i

= 1, ... , n;

k

= 1, ... , n),

i
is justified, which means that the set of the index pairs i, k with 1 ~ i < k ~ n shall be labeled in any arbitrary serial order and that then the product is formed. In any group the Oth and the negative powers of an element a may be defined as usual by aO = 1, a -n = (-1)" a , 4For k ::::: 1 the first factor drops out, for k ::::: n the second; this, however, has no effect on the proof.

The Concept of a Group

19

and we can prove without difficulty that the rules (2.2) and (2.3) are valid for any integral exponents. In an additive group we write of course

r "

Q,

instead of

1

11 a." R

1

and accordingly, .

n' a instead of cI'. In the additive group of the integers this definition is in agree-

ment with that of the product of two integers. All proofs given for products may now be applied to sums. Under the law of addition, rule (2.3) assumes the form of an associative law

noma

= nm-a,

whereas (2.2) has the form of a Udistributive law"

ma+na

= (m+n)a.

Another distributive law may be added to the two preceding laws, namely

m(a+b)

= ma+mb

[for multiplication: (ab)'" = amb'"] , which, however, holds only for Abelian groups. This is easily proved by induction_

Exercises 2.5. Prove for Abelian groups that m

m"

n n all' = n na,lY• II

.,=1 ,,=1

,,=1 1'=1

2.6. Similarly, prove

2.7. The order of the symmetric group 6,. is n! = tion on n.)

n"

v. (Mathematical induc-

1

2.2 SUBGROUPS For a nonempty subset 9 of a group 03 to be itself a group, provided the rule of combination for the elements of 9 is the same as that for the elements of (fj, it is necessary and sufficient that 9 fulfill postulates 1, 2, 3, and 4. Postulate 1 requires that if a and b lie in g, ab has to lie in 9 too. Postulate 2 is of course fulfilled for g, since it is fulfilled even for 6). Postulates 3 and 4 state that the identity lies in 9 and that if g contains Q, it also contains the inverse element a-I. AgaiR, the requirement for the identity is superfluous; for if a is any element in g,

20

GR.OUPS

then a-I also lies in g, and so does the product aa- 1 = e. Thus we have proved the following.

For a nonempty subset 9 of a given group
If 9 contains a and b it also contains their product, qb. 2. If 9 contains a it also contains the inverse a -1 of a. 1.

If, in particular, 9 is finite, even the second of these requirements is unnecessary; for in this case postulates 3 and 4 may be replaced by 6, and since 6 applies to 0;, it will surely apply to g. In general, postulates 1 and 2 can be replaced by one single postulate: If a and b are elements of g, 9 shall also contain ab -1 ; for if 9 contains a it also contains QQ-l == e and ea- 1 == a-I; hence, if 9 contains a and b it also contains b- 1 and a(b- 1)-1 == abe If(in Abelian groups) the group relation is additive, a subgroup is characterized by the fact that it contains a + b when it contains a and b, and - a, when it contains Q. These two postulates can be replaced by the single postulate that the subgroup shall contain a-b if it contains a and b. EXAMPLES OF SUBGROUPS Any group contains as a subgroup the identity group (t consisting only of the identity. The most important subgroup of the symmetric group 6,. of all permutations on n objects is the alternating group ~, containing those permutations which, when applied to the variables Xl' ••• , X n, carry the function .; (2.4)

into itself. These permutations are called even, the others odd. Odd permutations reverse the sign of the function fl. Any transposition (that is, a permutation on two digits) is an odd permutation. The product of two even or of two odd permutations is even; the product of one even and 'one odd permutation is odd. It follows from the first property that ~n is a group. Since a fixed transposition multiplied by an even permutation yields an odd one, and vice versa, there exist as many even permutations as there are odd ones; therefore there are n!/2 of each kind (cr. Exercise 2 . 7). In order to facilitate the notation of the subgroups of the symmetric group 6 n, the well-known symbols for cyclic or circular permutations are used. By (pqrs) we shall denote a cyclic permutation, carryingp into q, q into r, and r into s, and s into p, leaving the rest of the objects fixed. It is easy to show that any permutation is uniquely expressible (except for the order of succession) as a product of such cyclic permutations or "cycles" as

(ikl . ..) (pq ...) ... ,

Subgroups

21

where no two cycles have an element in common. The factors of this product commute. A cycle containing one element, for example, (1), is the identity permutation. It is understood that (1 2 5 4) = (2 5 4 1), and so forth. Employing these symbols, we may represent the 3! = 6 permutations of the group 6 3 thus: (1), (1 2), (1 3), (2 3), (1 2 3),. (1 3 2).

It is easy enough to determine all the subgroups. They are (besides 6 3 itself): ~3:

(1), (1 2 3), (1 3 2)

62: (1), (1 2) {

E5~:

(1), (1 3)

G5~:

(1), (2 3)


d'a rn =

(/'+m

= a"'ti',

this group is an Abelian group. A group consisting of the powers of a single element is called cyclic. Now there are two possibilities. Either all powers a" are distinct; then the cyclic group 0 1 2 ... ,a -2 ,a -1 ,a,a,a, ...

is infinite. Or it may occur that

d' = tf, h>k. Then Ja-i a-

=e

(h-k>O).

In this case let n be the smallest positive exponent for which d' = e. Then the powers aO, at, a2 , ••• , tf'-l are all distinct from each other; for (O~k
would imply

d'-l

=

e

(O
which is contrary to the assumption made as regards n.

22

GROUPS

If every integer m is represented in the form m = qn+r

(O~r
then

am = d'n+r = d'ncl = (d')q" = eel =

a.

Thus all powers of a are already contained in the sequence aO, ai, ... , tI' -1. The cyclic group, therefot:e, has exactly n elements, namely o 1 ... ,u.-II-I • a,a,

The number n, which is the order of the cyclic group generated by a, is known as the order of the element Q. If all powers of a are distinct from each other, a is called an element of infinite order. EXIllllpIe: The integers . . . , - 2, - 1, 0, 1, 2, . . . with addition as the rule of combination form an infinite cyclic group. The groups 6 2 and ~3 are cyclic groups of orders 2 and 3.

Exercises 2.8. 2.9.

There are cyclic permutation groups of any given order. Prove by induction on n that the n-I transpositions (I 2), (~ 3), ... ( 1 n) for n> 1 generate the symmetric group 6 n • 2.10. Prove, as in 2.9, that for n> 2 the n - 2 cyclic permutations on three digits (1 2 3), (1 2 4), ... , (1 2 n) generate the alternating group m:n• We shall now determine all subgroups of the cyclic groups. Let OJ be a cyclic group generated by a, and let 9 be a subgroup not consisting of the identity alone. If 9 contains an element a- m with a negative exponent, it will also contain the inverse element alii. Let am be the element of 9 having the smallest positive exponent. We shall prove that all elements of 9 are powers of am. If a' is an arbitrary element of g, we have

s = qm+r

(O~r<m).

Now t/(am)-q = d- mq = d is an element of g, where r<m, whence it follows that r = 0 because of the choice of m, and therefore s = qm and t/ = (amy'. Thus all elements of 9 are powers of am. If a is of finite order n so that ti' = e, then n must be divisible by m: n = qm, since d' = e is in the subgroup g. The subgroup 9 then consists of the elements a"', a2111 , ••• , film = e and is of order q. If, on the other hand, a is of infinite order, the subgroup 9 consisting of the elements e, a±'", a±2"" ... is likewise of infinite order. Thus we have proved the following.

Co~kx~.Couu

n

A subgroup of a cyclic group i9 itself cyclic. It consists either o/just the 1, or of the powers of the element am with the smallest possible positive m; in other words, it consists of the mth powers of the elements of the original group. For a cyclic group 0/ infinite order, m mIly be chosen at will, whereas .for a cyclic group of finite order n the number m must be a factor of n. In this case the subgroup is of order q = n/m. To every such number m belongs one, and only one, subgroup {aIN} of the cyclic group {a}.

2.3 COMPLEXES. COSETS In group theory a complex is defined as an arbitrary set of elements of a group ffi. By the product gl) of two complexes 9 and I) we understand the set of all products gh where g is taken from g, and h from I). If in the product gf;) one of the complexes, 9 for example, consists of only one element g, we may simply write gl) instead of gf). Obviously, the- following rule holds: g~f)

= (gl)f.

In composite products of complexes the parentheses may therefore be omitted [cf. (2.1)]. If the complex g is a group, then gg

= g.

Let 9 and 1) be subgroups of ffi. The question arises: Under what conditions is the product 99 itself a group? The totality of the inverses of the elements of 99 is 1)g, since the inverse of gh is h -1 g -1. Thus, for 91) to be a group, it is necessary that

l)g

= gl);

(2.5)

that is, 9 must commute with 1). This condition is also sufficient, for if it is satisfied, gl) contains for every gh also the inverse h- 1g- 1 and, moreover, for any two elements also their product, since gl)gl) = 991)9 = gl). Restating the above, we say: The product 99 of two subgroups g and 1) of OJ is itself a group if and only if the subgroups 9 and ~ commute. It is of course not necessary that each element of g commute with each element of I). If condition (2.5) is satisfied, then the product gl) is the group generated by 9 and~. In an Abelian group, (2.5) is always satisfied. If we write the Abelian group under the law of addition, that is, if 9 and 1) are submodules of a module, we write (g, 1) instead of 91), and we shall reserve the symbol 9 +9 for the special case of the "direct sum" to be investigated later.

24

GROUPS

H 9 is a subgroup, and a an element of (f), then the complex ag is called a left coset, and the complex ga a right coset (or a residue class) of gin (fj. If a lies in g, we have ag = g; hence one of the left (and also one of the right) cosets of 9 is always equal to 9 itself. In the following we shall mainly be concerned with left cosets, although all our considerations are valid for right cosets as well. Two co sets ag, bg can very well be equal without a being equal to b; for whenever a- 1 b lies in g, we have bg

= aa-1bg = a(a- 1bg) = age

Two different cosets have no common element; for if the cosets ag and bg have a common element, say

it follows that

glg2 -1 = a- 1b,

so that a-1b lies in g; accordingly, ag and bg are identical. Every element a belongs to a coset, namely to the coset age The latter surely contains the element ae = a. According to what has just been proved, the element Il belongs to just one coset. Therefore we may regard any element a as a repre.. M!1Jtative of the coset ag containing Q. According to the preceding paragraphs, the eosets constitute a partition of the group
.

N

} = -. n SGalois' notation GJ

= alQ+a2Q+

. • .

is often found in the literature, which means that the partitions are mutually exclusive and form the group QS. We avoid this notation because we want to reserve the + symbol for the direct sum to be discussed later on. 61t is true that the relation also holds when N is infinite; in this case, however, in order to explain its meaning, one has to introduce cardinal numbers, which we have not done.

Isomorphisms and Automorphisms

25

Theorem: The order of a finite group is divisible by the order of each one of its subgroups.' If, in particular, we consider a cyclic group generated by an element c as the subgroup, we have the following corollary. Corollary: The order of an element of a finite group is a factor of the order of the group. An immediate consequence of this theorem is that in a group of n elements the relation ti' = e holds for every Q. It may happen that all left cosets ag are likewise right cosets. To fulfill this condition, it is necessary that the left coset containing an arbitrarily given element a be identical with the right coset containing a; that is, for every a we must have (2.7) ag = ga. A subgroup 9 having the property (2.7), that is, commuting with every element a of (fj, is called a normals divisor, or a self-conjugate or invariant subgroup in (fj_ If g is a normal divisor, then the product of two cosets is itself a coset:

ag-bg

= a·gb-g = abgg = OOg. Exercises

2.11. Find the right and left cosets for the subgroups of the (53 group. Which of these subgroups are normal divisors? 2.12. Show that for any subgroup the inverses of the elements of a left coset form a right coset_ Conclude from this that the index may also be determined as the number of the right cosets. 2.13. Show that any subgroup of index 2 is a normal divisor. Example: the alternating group of the symmetric group of n letters. 2.14. A subgroup of an Abelian group is always a normal divisor. 2.15. If (fj is a cyclic group generated by a, and 9 a subgroup distinct from (t and generated by am with the smallest m (see Section 2.2), then 1, a, a2 , ••• ,am - 1 are representatives of the cosets, and m is the index of 9 in (!). 2.16. If the product of any two left cosets of 9 in is itself a left coset, 9 is a

m

nonnalsubgroupin~.

2.4 ISOMORPHISMS AND AUTOMORPIllSMS Let two sets IDl and un be given. Let there be defined any sort of relations between the elements of each of these sets. We may, for example, imagine that 7Translator's note: This theorem is also known as Lagrange's theorem. 8Here "divisor" means subgroup. "Normal" expresses the special property ag = gao Translator's note: This group is sometimes called a Udistinguished" subgroup, a literal translation of the German "ausgezeichnet."

26

GROUPS

the sets ID1 and ml are groups, and that the relations are the equations a·b == c, which exist by virtue of the group property; or we may think of ordered sets with relations a> h. lfit is possible to place the two sets into one-to-one correspondence so that the mapping preserves the relations; that is, if with every element a ofIDl there can be associated an element Ii ofIDl in a biunique manner so that the relations existing between any elements a, b, ... of IDl also exist between the associated elements a, b, . .. and vice versa, then the two sets are called isomorphic (with respect to the relations in question), and we write IDl ~ IDl. The ~apping itself is called an

i.Iomorphism. Thus we can speak of isomorphic groups, of isomorphically ordered or similarly ordered sets. An isomorphism of two groups is therefore a one-to-one mapping a~, where ab == c implies db = c (and vice versa), and where therefore the product ab is always associated with the product db. Just as in the general theory of sets, sets of the same cardinality are equivalent, so in the theory of order types, similar sets and, in group theory, isomorphic groups are not to be regarded as substantially different from one another. Concepts and theorems which can be defin~d and proved on the basis of the given relations of a set may be applied directly to any isomorphic set. For example, a set for which product relations are defined and which is isomorphic with a group is itself a group, and the isomorphism sends the identity, inverses, and subgroups into the identity, inverses, and subgroups. If, in particular, the two sets 9R and IDl are identical, that is, if the mapping under consideration associates with every element a an element d of the same set in a one-to-one manner, and if the relations are preserved, then the mapping is called an automorphism. The automorphisms of a set are an expression of its symmetry, for what is meant by symmetry, such as the symmetry of a geometric figure? It means that, under certain transformations (such as reflections or rotations), the figure is mapped upon itself, whereby certain relations (such as distances, angles, relative locations) are preserved; or, if we use our own terminology, we may say that the figure admits certain automorphisms relative to its metric properties. Obviously, the product of two automorphisms (product of transformations, according to Section 2.1) is itself an automorphism, and the inverse operation of an automorphism is again an automorphism. According to Section 2.1, it follows that the automorphisms of an arbitrary set (with arbitrary relations between its elements) form a transformation group, the automorphism group of the set. In particular, the automorphisms of a group form a group themselves. Let us investigate some of these automorphisms a little more closely. Let a be a fixed group element. The mapping carrying x into

x = axa- 1 is an automorphism, since first 0.8) may be solved uniquely for x: x '= a-1xa,

(2.8)

Isomorphisms and Automorphisms

27

which implies that the mapping is one-to-one; second, we have

xy

= axa- 1 'aya- 1 = a(xy)a- 1 = xy;

therefore the mapping is isomorphic. The elements x, axa- 1 are called conjugate group elements. The automorphisms x~axa-l generated by the elements a are called inner automorphisms of the group. All other automorphisms (if they exist) are called outer automorphisms. An inner automorphism x~xa -1 transforms a subgroup 9 into a subgroup aga- 1 , which is said to be a conjugate of g or conjugate to g. If a subgroup 9 is identical with all its conjugate subgroups, that is, aga- 1

=9

for every a,

(2.9)

it simply means that the group g commutes with every element a, that is, ag = ga,

and is, therefore, a normal divisor (Section 2.3). We may restate the above as follows. The subgroups invariant under all inner automorphisms are the normal divisors. This theorem explains why normal divisors are also called invariant subgroups or self-conjugate subgroups. Postulate (2.9) may be replaced by the slightly weaker postulate aga- 1 ~ g,

(2.10)

for if (2.10) is true for every a it will be true for a- 1 as well: a- 1 ga c g,

gc

aga~l;

(2.11)

now (2.9) follows from (2.10) and (2.11). Thus we may say the following. A subgroup is a normal divisor if it contains with any element b all its conjugate elements aba- 1 as well. Exercises

2.17.

Abelian groups have no inner automorphisms except the identity auto.. morphism. , 2.18. In permutation groups the transform aba~l of an element b can be obtained by expressing b as a product of cycles (Section 2.2), and by performing the permutation a on the digits of these cycles. Give the proof. Use this proposition to compute aba-·1 for

b = (1 2) (3 4 5) a = (234 5). 2.19. Prove that the symmetric group 6 morphisms.

3

has no outer, but six inner auto ..

28

GROUPS

2.20. The symmetric group 6 4 has, besides itself and the identity group, only the following normal divisors: a. The alternating group ~4' b. Klein's four-group ~4' consisting of the permutations

(1), (1 2) (3 4), (1 3) (2 4), (1 4) (2 3). The latter group is Abelian. 2.21. If 9 is a normal divisor in (fj, and if ~ is an intermediate group gc~~<»

then 9 is likewise a normal divisor in ~. 222. All infinite cyclic groups are isomorphic with the additive group of integers. 223. The conjugation relation is symmetric, reflexive, and transitive. It is thus possible to partition the elements of a group into classes of conjugate elements.

2.5 HOMOMORPIDSMS, NORMAL SUBGROUPS, AND FACTOR GROUPS H in two sets IDl and 91 certain relations are defined (such as a < b or ab = c) and if to each element a ofIDl an image Ii = cpa is assigned in such a manner that all relations between the elements of IDl also hold for the images (so that, for example, a < b implies d < h in the cases of the relation <), then cp is called a homomorphic mapping or a homomorphism from 9'R to 91. For example, let IDl be a group and 91 a set in which a product is defined. If then the product Db is always mapped to the product ti· b, then the mapping is a group homomorphism. The (one-to-one) isomorphisms of groups previously defined are examples. If the mapping tp is surjective, that is, if each element of 91 is the image of at least one element a ofm, then cp is a homomorphism of Wl onto 91. A homomorphic mapping of IDl into itself is called an endomorphism. In the case of a homomorphic mapping ofIDl onto ~Jl, the elements ofIDl which have a fixed image d in IDl can be put into a class Q. Each element a belongs to one and only one class Q; that is, the set IDl is partitioned into classes which are in one-to-one correspondence with the elements of 9Jl. The class a is called the inverse image of ti. Emmple: If every element of a group is mapped upon the identity, a homomorphism of the group with the identity group is produced. Homomorphism can also be obtained by associating with each permutation of a permutation group the number + 1 or - 1, depending on whether the permutation is even or odd; the associated group is the mUltiplicative group of the numbers + 1 and -1. If we associate with every integer m the power am of an element a of a group, we obtain a homomorphism of the additive group of integers with the cyclic

Homomorphisms, Normal Subgroups, and Factor Groups

29

group generated by a, since the product a",+n = am.", is associated with the sum m+n. If a is an element of infinite order, the homomorphism is an isomorphism. Now we shall, in particular, investigate homomorphisms of groups. Theorem: If, in a set (fj, products db (that is, relations of the form dh = c) are defined, and if a group (fj is mapped homomorphieally upon (fj, then (fj is itself a group; or briefly, the homomorphic image ofa group is itselfa group. Proof: First of all, any three given elements a, h, c of ffi are always images of elements of (fj, for example, of a, b, c. From

ah·c

= a·bc

now follows

dO·c = d·he. Furthermore, ae = a

for all a

de =d

for all ti,

implies

and ba = e implies

hd

=

e.

Thus there is an identity e in 6) and an inverse for every d. Therefore., (fj is a group. At the same time we have proved the following. Under any homomorphism the identity goes into the identity, and inverses go into inverses. We shall now study in greater detail the partition effected by a homomorphic mapping (fj~(fj, and we shall find a very important one-to-one relation between homomorphisms and normal divisors. Theorem: The class e 0/0), to which corresponds the identity e o/(fj under the homomorphism (fj~(fj, is d normal divisor of·(fj, and the other classes are the eosets of the normal divisor. Proof: In the first place, e is a group; for if the homomorphism carries both a and b into e, then it carries ab into e2 = e; thus e contains, along with any two elements, their product. Furthermore, a-I is mapped upon e- 1 = e; thus e contains also the inverse of every element. The elements of a left coset ae are all carried into the element de = a. If, conversely, an element a' is mapped into a, then let x be determined from /

ax = a'. It follows that

ax

= d

x = e. Hence x lies in

e, and a' lies in ae.

30

GROUPS

The class of
ae

=

ea,

and e is a normal divisor. This completes the proof. The normal divisor e, the elements of which are mapped to eunder the given homomorphism, is called the kernel of the homomorphism. Let us now reverse the question. Let a normal divisor 9 of (fj be given. Is it possible to form a group ij) homomorphic with (fj so that the cosels of 9 correspond exactly to the elements of (fj ? In order to achieve this, we simply choose the cosets of 9 themselves as elements of the group <» to be constructed. 'According to Section 2.3, the product of two cosets of the normal divisor 9 is itself a coset, and if a belongs to the coset a9 and b to bg, then ab belongs to abg = ag' bg, the coset of the product. It follows that the cosets form a set homomorphic with <» and hence a group homomorphic with ffi. This group is called a quotient of ffi by 9 or a factor group of <» or a quotient group of{». It is denoted by (fj/ g.

The order of (fj/g is equal to the index of g. Here we realize the fundamental importance of normal divisors: they enable us to construct new groups homomorphic with given groups. If a group is mapped homomorphically onto another group ffi, we have seen that the eosets of the kernel e of (fj correspond (biuniquely) to the elements of
m

and in fact (ab)

= tI·D

because of the homomorphism. Thus we have

{fj/e

~ (f),

and the following homomorphism theorem for groups. lbeorem: Any group (fj onto which (fj is mapped homomorphically is isomorphic to the factor group CfJ/e, where the normal divisor e is the kernel of the homomorphism. Conversely, (fj is mapped homomorphically onto every factor group (fj/e (e is here a normal divisor).

Exercises 2.24. Trivial factor groups of any group (fj are

Homomorphisms, Normal Subgroups, and Factor Groups

31

2.25. The factor group of the alternating group (6n/m:J is a cyclic group of order two. 2.26. The factor group 6 4 /58 4 of the four--group (Exercise 2.20) is isomorphic with 6 3 2.27. The elements aba- 1b- 1 of a group
In an Abelian group every subgroup is a normal subgroup (cf. Exercise 2.14). If the law of combination is addition, the groups and their subgroups are known as modules, as has already been said. The cosets a+IDl (where IDl is a module) are called residue classes modulo IDl, and the factor group (J)/m is called the residue class module of
a

= b (mod rol)

or, briefly,

=b (rol). If a and b are congruent (modulo 9R), the residue classes aand h are identicaL Conversely, Ii = h always implies a =b(Wl). a

For example, the multiples of a positive integer m form a module in the domain of all integers, and we write accordingly

a

= b(m),

if the difference a - b is divisible by m. The residue classes may be represented by 0, 1, 2, ... , m -1, and the residue class module is a cyclic additive group of order m.

Exercise 2.29~

Any cyclic group of order m is isomorphic with the residue class module modulo an integer m.

Chapter 3

RINGS AND FIELDS

Definition of the concepts of a ring, an integral domain, a field. General methods for forming rings (or fields, respectively) from other rinSs. Theorems on factorization into primes in integral domains. The concepts of this chapter will be used throughout the book.

3.1 RINGS ~e quantities employed in algebraic and arithmetic operations

vary in nature; at times we use the integers, or the rational, the real, complex or algebraic numbers, and at other times we deal with polynomials, or rational functions in " variables, and so on. Later we shall become familiar with quantities of a completely different nature, such as hypercomplex numbers and residue classes, with which we can operate in the same or almost the same manner as with numbers. It is therefore desirable to arrive at a common concept embracing all these domains, and to investigate the rules of operation in these domains in general. By a system of double composition we shall mean a set of elements in which, for any two elements a, b, ... , a sum a+b and a product a·b belonging to the set are uniquely defined. A system of double composition will be called a ring if the following rules of operation are satisfied for all elements of the system: I

Laws of addition a. Associative law: a+(b+c)

= (a+b)+c b. Commutative law: a+b = b+a c. Solvability1 of the equation a + x = b for all a and b

II Law of multiplication a. Associative law: a· be ill Distributive laws a. a·(b+c) = ab+ae

= ab· c

b. (b+c)·a = ba+ca lA unique solution is not required.

32

Rings

33

Addendum: A ring is called commutative if the commutative law holds for the multiplication: lIb. a·b = b·a.

For the present we shall mainly deal with commutative rings. REGARDING THE LAWS OF ADDITION The three laws la, Ib, Ic merely assert that the ring elements form an Abelian group under addition . 2 Consequently, we can apply to rings all theorems proved for Abelian groups. There exists one (and only one) zero element 0 such that for every a.

a+O = a

Moreover, for every element a, there exists a negative -a such that

-a+a =

o.

Furthermore, not only is the equation a+x = b solvable, but the solution is unique; its sole solution is x = -a+b, which we denote also by b-a. By virtue of

a-b

= a+(-b)

any difference may be written as a sum. In this sense, differences obey the same rules for permuting terms as do sums; for instance,

(a-b)-e = (a-e)-b. Finally -( -a) = a and a-a =

o.

REGARDING THE LAWS OF ASSOCIATIVITY As we saw in Section 2.1, it is possible, on the basis of the associative law for multiplication, to define the composite products n

Il1 a" = a1 a2 · · .an and to prove their characteristic property Jft"

m+ra

Il a,,· Il am +" = Il aye 1

y=1

1

Similarly, we define the sums 11

"a ~ y

= a1 +a2... 1+a 1

1

2This group is known as the additive group of the ring.

34

RINGS AND FIELDS

and prove their characteristic property

By virtue of Ib, the terms of a sum may be interchanged at will, and in commutative rings the same may be done for products.

REGARDING THE LAWS OF DISTRmUTIVITY Whenever the commutative law of multiplication holds, IIIb is, of course, a consequence of IlIa. By induction on n it follows at once from IlIa that a(b 1 +b 2 +

· · · +bn}

= ab 1 +ab2

+ · · · +ab,.,

and from IIIb that

Combining these two relations, we obtain the well-known rule for the multiplication of sums:

+ ........ . +a"b 1 +

... + a,/J".

The distributive laws hold for subtraction as well, for instance, a(b-c) = ab-ac,

as can be seen from

a(b-c)+ac

= a(b-c+c) = abe

In particular a·O

= a(a-a) = a·a-a-a = 0,

or in words: a product is zero whenever one of its factors is zero. The" converse of this theorem is not necessarily true, as will be seen from examples shown below. It may happen that where a =f= 0, b =f=

o.

In such a case a and b are called zero divisors or divisors of zero, a being a left and b a right zero divisor. (In commutative rings these two definitions coincide.)

Rings

35

For the sake of expediency the zero itself is considered a zero divisor. Thus a is called a left zero divisor, if there exists a b =+= 0 such that ab = o. 3 If there are no zero divisors in a ring except zero itself, that is, ab == 0 implies a = 0 or b == 0, the ring is called a ring without divisors of zero. If, moreover, the ring is commutative, it is also known as an integral domain. Example: All examples mentioned in the beginning (ring of integers, ring of rational numbers, and so on) are rings without zero divisors. The ring of the continuous functions in the interval (-1, + 1) does have zero divisors; for~ putting f = f(x) = max (0, x), g

we have f

=+=

0,4 g=t=O, fg =

= g(x) = max (0, -x),

o. Exercises

3.1. The pairs of integers (ai, a2) with (ai' a2)+(b 1, b2)

= (al +b1, a2 +b2)

(aI' a2 )·(b 1 , b2 ) = (alb l , Q2b2) form a ring with zero divisors. 3.2. It is permissible to cancel a in an equation ax = ay, provided a is not a left zero divisor. (In particular, it is possible to cancel any a =F 0 in ali integral domain.) 3.3. Taking as an additive group any arbitrary Abelian group, construct a ring in which the product of any two elements is equal·to zero.

THE IDENTITY If a ring has a left identity e,

ex = x

for every x,

and simultaneously, a right identity e',

xe'

==

x

for every x,

then the two identities must be equal, since e

= ee' = e'.

Thus every right identity is equal to e, and so is every left identity. Then e is simply called the identity, and a ring containing such an element is called a ring 3Assuming

that there is at least one element nonzero in the ring.

414:-0 means: 1 is a function, distinct from zero, but it does not mean that f does not vanish anywhere.

36

RINGS AND PIBLDS

with unity element. Frequently, the identity is denoted by 1, although it has to be distinguished from the number 1. The integers form a ring l with identity; the even numbers, a ring without identity. There are also rings with one or more right identities but without a left identity, or vice versa. THE INVERSE ELEMENT

If a is an arbitrary element of a ring with identity e, then, by a left inverse of a we shall understand an element lZ(.I>1 such that -1

D(I>

a = e,

and by a right inverse an element a(;)1 such that -1

DD(r) =

e.

If an element a has both a left 'and a right inverse, then both are equal, since

ot."L/

= a(l)l(aa(;)l) =

(~(i/a) a(,.)l

= a(;/,

and hence each right inverse as well as each left inverse of a is equal to this one. In this case we say: a possesses an inverse element, and we denote the inverse by a-I. POWERS AND MULTIPLES We saw already in Chapter 2 that, by virtue of the associative law, the powers d' (II is a positive integer) may be defined for every ring element a, and that the well-known rules hold: (/'·a'"

(c(')m (ab)-

= d'+m = tflll = tfb-,

(3.1)

the last equality holding for commutative rings. If the ring has an identity, and if a has an inverse, we may introduce the Oth and negative powers (Section 2.1); the rules (3.1) remain valid. Since any ring is an additive group, the multiples

noa

(= a+a+

° • •

+a, with n terms)

may be defin~, and we have:

na+ma =- (n+m)a

noma = nmoa n(a+b) = na+nb n·ab = na-b = a·nb.

(3.2)

Rings

37

If we define

(-n)·a = -na, just as for powers, the rules (3.2) will hold for all integral n's and m's (positive, negative, or zero). The expression n 'a should not be regarded as a real product of two ring elements; for, in general, n is not a ring element, but something introduced from the outside: an integer. However, if the ring bas the identity e, then na may be written as a real product, namely

na

= n'ea = ne·a. Exercises

3.4. A left zero divisor has no left inverse; a right zero divisor has no right inverse. In particular, the zero element has neither a right nor a left inverse. A trivial exception is the ring consisting of but one element 0, which, simultaneously, is the identity and its own inverse. 3.5. Prove for arbitrary commutative rings the binomial theorem: (a+b)"

= d'+(i) tf-lb+(~) ",-2b 2 +

by induction on n. Here

· · · +b",

ID denotes the integer

n(n-l) ... (n-k+l) n! ----1-2 ... k (n-k)!k!

3.6. In a ring with exactly n elements we have for every a: n'a = O. [Cf. Section 2.3, where d' = e was proved.] 3.7. If a commutes with b, that is, if ab = ba, then a also commutes with -b, with nb, and with b -1. If a commutes with band c, then a also commutes with b+c and with bc. FIELDS A ring is called a skew field, s if a. It contains at least one element distinct from zero; b. There is always a solution for the equations ax

=b

ya = b

for a

=1=

O.

(3.3)

5Some authors extend the term "field" to all skew fields and make a distinction between commutative and noncommutative fields.

38

RINGS AND FIELDS

If, in addition, this ring is commutative, it is simply called a field or a domain of rationality, sometimes a commutative field. From (a) and (b) we prove, just as for groups (Chapter 2): c. The existence of a left identity e; solve the equation xa = a for any a += 0, and call the solution e. For an arbitrary b, solve ax = b; it follows that

eb

= eax = ax = b.

Similarly, the existence of a right identity may be proved, and thus we have prpved the existence of an identity. Moreover, from (b) follows at once: d. The existence of a left inverse a-I for every a =t= O. As in the case of groups, it can be shown that the left inverse a-I is at the same time a right inverse.

As in the case of groups, we may show that, conversely, (b) follows from (c) tmd{d).

Exercise 3.8. Carry out the proof of the above. A. skew field has no zero divisors; for by multiplying ab = 0, a =F 0, by a- 1 , it follows at once that b = O. Equations (3.3) have unique solutions, for from the existence of two solutions x, x', say, of the first equation it would follow that

ax = ax', and upon mUltiplying by a-Ion the left:

x

= x'.

The solutions of (3.3), of course, are

= a-1b y = ba- 1 •

x

In the commutative case we have a- 1 b

= ba- 1 ; for this we may write bla.

In a skew field the nonzero elements form a group under multiplication, namely the multiplicative group of the skew field. Thus a skew field unites in itself two groups, the multiplicative and the additive groups. They are connected by the distributive laws. EXIUlfPIe 1: The rational numbers, the real numbers, the complex numbers form commutative fields.

Homomorphism and Isomorphism

39

Example 2: A field containing only two elements 0 and 1 may be constructed as follows: Multiply the elements like the numbers 0 and 1. For addition, let 0 be the zero element:

0+0

= 0,

0+1=1+0=1;

furthermore, let 1 + 1 = O. The rule of addition is the same as the rule of combination for a cyclic group of two elements (Section 2.2) ; thus the laws of addi tion hold. The laws of multiplication hold, since they are valid for the ordinary numbers 0 and 1. The first distributive law is proved by enumerating all possibilities. As soon as a zero occurs in it, it becomes trivial; therefore, we need verify only 1 · (1 + 1)

= 1· 1 + 1 · 1,

which yields 0 = o. Finally, the equation 1· x the solution is x = a.

=

a has a solution for every a;

Exercises 3.9.

Construct a field of three elements. (First discuss what structures the additive and the multiplicative groups may have.) 3.10. An integral domain with a finite number of elements is a field. (Compare the corresponding theorem for groups in Section 2.1.)

3.2 HOMOMORPmSM AND ISOMORPmSM Let 9t and 6 be systems with double composition~ According. to the general definition in Section 2.5, a mapping cp of 9t into (5 is a homomorphism if the relations a + b = c and ab = d are preserved by the mapping, that is, if the sum a+b is mapped onto d+h and the product a"b onto a-b. The image 9t of9t is called a homomorphic image of £ft. If the mapping is one-to-one, it is an isomorphism in the sense of our general definition (S-ection 2.4), and we write 9l ~ m. The relation m ~ (5 is reflexive, transitive, and also symmetric, since the inverse mapping of an isomorphism is again an isomorphism. Theorem: The homomorphic image of a ring is· itself a ring. Proof: Let 9i be a ring, 9i a system of double composition, and 9l",,9t We have to show that mis itself a ring. The proof is the same as that for groups (Section 2.5): . If a, b, c are any three elements of m, and if any rule of operation is to be proved, for instance, d(b+c) = iih+ac, then three inverse images (preimages) a, b, c can found for a, h, c. Since 9t is a ring, a(h+c) = ab+ac, and it follows that d(h + c) = db + de because of the homomorphism. The same procedure may be applied to all laws of associativity, commutativity, and distributivity. In order

be

40

lUNGS AND FIBLDS

to prove the solvability of the equation d+x = h, we again take inverse images a, b, solve a+ x = b, and then, because of the homomorphism, we have d +x = b. 1heorem: A homomorphism sends the zero element o/9t into the zero element of 91 and the negative - a of each element a of 91 into the negative in 9t of the corresponding element d. Jf9t has an identity e, it goes over into the identity of9t. Proof: As in the case of groups. Evidently, if 9t is commutative, so is 9t. If 91 is an integral domain, 91 need not be one, as we shall see afterwards; similarly Mmay be an integral domain without ~ being one. However, if we are dealing with an isomorphic mapping, then, of course, all algebraic properties are carried over from 9t into 9f, and it follows that an isomorphic image ofan integral domain or of afield is, respectively, an integral domain or afield. A theorem which apparently is trivial in this connection, but which will prove very useful in the sequel, is the following: 1heorem: Let 9t and 5' be two distinct rings. Let 5' contain a subring 9t' isomorphic with 9t. Then there exists a ring 6 ~ 6' which includes 9t itself. Proof: From 6' we eliminate the elements of 91' and replace them by the elements of 91 to which they correspond under the isomorphism. Now we define the sums and products for the unreplaced and replaced elements so that they correspond exactly to the sums and products in 6'. (If, for example, before the replacement, a'b' = c', and if a' is replaced by a, while b' and c' remain unaltered, we define: ab' = c'.) In this fashion we obtain from 6' a ring <5 ~ 6' which in fact includes

m.

3.3 THE CONCEPT OF A FIELD OF QUOTIENTS If a commutative ring 9t is embedded in a skew field a, we may form quotients in n from the elements of 9t thus: 6

For them the following rules of operation hold:

a c - =b d

if and only if, ad = bc

(3.4)

6From ab

= ba follows ab -1 = b-1a on multiplying by b -Ion the left and on the right.

The Concept of a Field 0/ Quotients

41

F or if we multiply both sides of each equation by bd, we get the same result in each case; and bdx = bdy implies x = y. Thus we can see that the quotients alb form a commutative field P, called the field of quotients of the commutative ring m. Furthermore, it can be seen from (3.4) that the manner in which fractions are compared, added, and multiplied will be known, whenever these operations can be performed on their numerators and denominators, that is, on the elements of 9t; in other words, the structure of the field of quotients Pis completely determined by that of9t, or :fields ofquotients o/isomorphic rings are isomorphic. In particular, any two fields of quotients of a single ring are always isomorphic, or: the field of quotients P is, except for iso-

morphism, uniquely determined by the ring 9t, provided there exists at all a field of quotients for the ring 9t. Now the following question arises: What commutative rings possess a field of quotients, or, which is the same thing, what commutative rings can be embedded in a field? In order that a ring 9t may be embedded in a field, it is first necessary that there be no zero divisors in 9{, for a field has no zero divisors. In the commutative case this condition is also sufficient: Any integral domain ~ can be embedded in a

field.' Proof: We may disregard the trivial case where 9.l consists only of a zero element. Let us consider the set of all pairs of elements (a, b), where b =F o. With these pairs we shall later associate fractions alb. Let (a, b) "" (e, d) if ad be. [Cf. the above formulae (3.4).] The relation f"'-.J thus defined is obviously reflexive and symmetric; it is likewise transitive, since from (e, d) f"'-.J (e,/) (a, b) "" (c, d), it follows tliat

=

ad = bc,

cl= de;

hence adf = bel = bde. This implies, sipce d =1= 0 and 9t is commutative,

a/= be, (a, b) ""' (e,/). Consequently, the relation has all the properties of an equiValence relation and therefore defines (according to Section 1.5) a partition for the pairs (a, b), pairs being put in the same class if they are equivalent. Let the equivalence class containing (a, b) be symbolized by a/b. According to this definition alb = c/d when and only when (a, b) "" (c, d), that is, when ad = be. ,-....j

7For noncommutative rings without zero divisors this theorem does not hold any longer; see A. Malcev in Math. Ann., Vol. 113 (1936).

42

RINGS AND FIELDS /

In accordance with the earlier formula (3.4), we now define the sum and the product of the new symbols alb by: (3.5)

a c b d

ac bd

-.-=_.

(3.6)

The definitions are admissible for the following reasons. First, bd =t= 0 if b =F 0 and d =1= 0; (ad + be )/(bd) and (ac )/(bd) are therefore permissible symbols; second, the right-hand sides are independent of the choice of the representatives (a, b) and (c, d) of the classes alb and c/d; for replacing a and bin (3.5) by a' and b', where.

ab' = ba',

we find adh' = a'db adh'+bcb' = a'db+b'cb (ad+be)b'd = (a'd+b'c)bd; hence

a'd+b'e ad+be ---b'd bd Similarly,

ab' = ba' aeb'd = a'ebd

Similar results will be obtained when (c, d) is replaced by (e', d'), where cd' = de'. We can show without difficulty that aJI field properties are fulfilled. The associative law of addition, for example, is obtained thus:

~

(:. =) -_~b + e/+de _ ad/+bcf+bde df bdf

b + d+ f

(~b + d

:.)

:. =

+f

ad+bc ~ _ ad/+bc/+bde bd +fbd/ '

and the other laws are obtained in the same way. Evidently, the field constructed is commutative. If it is to include the ring 91, certain fractions have to be identified with elements of9l. This is done as follows: We associate all fractions (cb)/b with the element c, where b =t= O. These fractions are all equal: since (cb)b' = b(cb').

Polynomial Rings

43

Thus, with every element c there is associated only one fraction, and distinct fractions are associated with distinct elements c, c', for it follows from cb

c'b'

b=-V that ebb' = be'b', Of,

since b

=1=

0, b' =f= 0, we may divide each member by bb' and have

c = c'. Therefore these fractions are in a one-to-one correspondence with the elements

ofm. If c 1 + C2 =

C3 or c 1 C2 = C3 are in 9t, it follows for arbitrary b 1 and b 3 = b 1b 2 that, respectively,

=1=

0, b2 =t= 0,

and Cl b l C2 b 2

--0--

b1

b2

==

C 1 C2 b l b 2

b 1b 2

b b3

C3 3 = --.

The associated fractions (cib,)/bi thus add and multiply exactly as the ring elements Ci; they form a domain isomorphic with m. Consequently, we may replace the fractions (cb}/b by the corresponding elements c (end of Section 3.2). We thus find a field including the ring 9t. Thus, for every integral domain 9t, we have proved the existence of a field containing m. The formation of quotients is the first tool we employ for obtaining rings or fields from other rings. Thus, for example, from the ring lL of the ordinary integers the field Q of rational numbers is derived by this method.

Exercise 3.11. Show that any commutative ring 9t (with or without a zero divisor) can be embedded in a "quotient ring" consisting of all quotients alb, with b not a divisor of zero. More generally, b may range over any set IDl of nondivisors of zero which is closed under multiplication (that is, b 1, b 2 is in m when b i and b2 are). The result is a quotient ring ~:

3.4 POLYNOMIAL'RINGS Let mbe a ring. With a new symbol x not belonging to mwe form the expression f(x)

=

L ayXv

44

RINGS AND FmLDS

in which the sum is taken over a finite number of different integers v ~ 0, and where the "coefficients" Dy belong to the ring 91; for example, f(x) = aOxo+a3x3+asx5.

These expressions are called polynomials; the symbol x is called an indeterminate. Thus an indeterminate is only a symbol, a letter, nothing else. Two polynomials are called equal only when they contain exactly the same terms, aside from terms with zero coefficients, which may be omitted or included at will. If we add or multiply polynomialsf(x) and g(x) according to the rules of high school algebra, assuming that all powers of x commute with the ring elements (ax' = x'a) and collect ternts with the same power of x, we obtain a polynomial cyX..,. In case of addition, we have

I:

(3.7) (taking a, = 0 or by = 0 if a y or by is missing), and in case of mUltiplication we have (3.8) We now define sum and product of two polynomials by formulae (3.7) and (3.8) and assert: The polynomials form a ring. The properties of addition are obvious, since addition of polynomials is reduced to the addition of their coefficients. The first distributive law follows from

and the second is obtained in a similar way. Finally the associative law of multiplication is obtained from

I:

«+t=v

a« (

L

P+"I=t

b,c"l)

= «+P+7=V L a)J,c"l

The polynomial ring derived from 91 is denoted by 9l[x]. If 9t is commutative, then 9t[x] is also commutative. The degree of a polynomial distinct from zero is the greatest number v for which a" =i= o. This a" is known as the leading or the highest coefficient. Polynomials of degree zero are of the form Qoxo. These polynomials may be identified with the elements ao of the original ring 9t. This identification is permissible, since these special polynomials form a system isomorphic with the original ring 91 (cf. end of Section 3.~~). Thus the polynomial ring 9t[x] includes m. The transition from 9t to 9t[x] is also known as the adjunction (in this case ring adjunction) of an indeterminate x. If we adjoin to the ring mthe indeterminates Xl' ••• , x n , successively (that is, if

Polynomial Rings

45

we form 9t[X 1] [X2] .•• [X,J), we obtain a polynomial ring 9t[x l' ... , xJ, consisting of all the sums By changing everywhere in such a polynomial the order of the factors Xl «, ••• , X"«"', the polynomial ring 9t[x 1] [X2] ... [xJ may be identified with the polynomial ring of the interchanged indeterminates, say with 9t[X2] [xJ ... [Xl]. This identification is permitted, since the interchanging of the Xi has no effect on the definition! of sum and product. 9t[x 1 , ••• , x,J is caIled the polynomial ring in the n indeterminates x l' • • . , x". In particular, if 9t is the ring of integers, we speak of integral polynomials. REPLACEMENT OF THE INDETERMINATE BY AN ARBITRARY ELEMENT OF THE RING If f(x) = L ayX" is a polynomial over 9t and or; is a ring element (from 9t or an overring of 9t) which commutes with all the elements of 91, then we may replace xbyor; in theexpressionforJ(x) and thus obtain theelementf(a;) = a"a;v. If g(x) is another polynomial and g(a;) is its value for x = lX, then the sum and the product f(x)· g(x) = p(x) f(x) + g(x) = s(x) ,

L

for x

=«

have the values J(<<) + g(a.)

" = s(a.),

f(a.)· g(a.) = p(a.).

This is obvious for the case of the sum. The computation for the case of the product follows from formula (3.8): p(a.)

= L c"a;"

=

L l+,,=y L aAb"a." = LA L aA,b,,«A+II l'

=

Il

(L ala;A) (L blla.f.I) = J(a.)g(a.).

We have thus proved the following. All relations between polynomials f(x), g(x), . . . involving mUltfplication and addition are preserved if x is replaced by any element o/the ring (X which commutes with all the elements olm. A similar theorem is also true for polynomials in several indeterminates. In particular, if 9t is commutative we may replace the indeterminates in the polynomial f(x It ••• x,,) by any element of 9t (or by any element of a commutative overring of 9t). Because of this possibility of substitution, polynomials are called integral rational Junctions of the variables x 1, ••• , x,.. In polynomials over the ring of integers without a constant term the substitution can be extended even further; we may substitute an element of any given ring for x, whether or not the ring includes the ring of integers. , If9t is an integral domain, so is 9t[x]. Proof: If f(x) =t= 0 and g(x) =t= 0, and if a« is the leading coefficient (distinct from zero) in /(x), and, similarly, if bp is the leading coefficient in g(x), then

46

RINGS AND FIELDS

*

0 is the coefficient of x«+' in I(x)· g(x); hence I(x)· g(x) o. Therefore there are no divisors of zero. From the proof we infer the corollary: If9t is an integral domain, the degree f(x)· g(x) is the sum of the degrees ofI(x) and g(x). For polynomials in n variables we have by induction: If9t is an integral domain, so is 9t[x l' · • · , x.J. By the degree of a term a(l, 1 ••• tlr XIII, ••• X/',. we mean the sum of the exponents ~CXi. By the degree of a nonvanishing polynomial we mean the highest of the degrees of the terms distinct from zero. A polynomial is said to be homogeneous or to be alorm if all of its terms are of the same degree. Products of homogeneous polynomials are themselves ~omogeneous, and the degree of the product is equal to the sum of the degrees of the factors if 9t is an integral domain. Nonhomogeneous polynomials may be expressed (uniquely) as sums of homogeneous constituents of various degrees. If we multiply two such polynomials f, g of degrees m and n respectively, then the product of the homogeneous constituents of highest degree is, in case of an integral domain 9t, a nonvanishing form of degree m+n. All the other constituents of/og are of lower degree; hence the degree off· g is again m+n. Thus the above mentioned corollary is also valid for polynomials in any number of indeterminates.

a.P_

=+=

THE DIVISION ALGORITHM If 9t is a ring with the identity 1 and if, furthermore,

g(x) =

LCyXY

is a polynomial with the leading coefficient f(x)

Cn =

1, and if

= LayXv

is an arbitrary polynomial of degree m ~ n, we can make the leading coefficient a", vanish by subtracting from I a multiple of g, namely a",x"'-"g. If after this subtraction the degree is still ~ n, we can again remove the leading coefficient by subtracting another multiple of g. Continuing in this way, we eventually lower the degree of the remainder to less than n and we have

f-qg = r,

(3.9)

where r is of lower degree than g, or equal to zero. This process is known as the

division algorithm. If, in particular, 9l is a field and g =+= 0, then the assumption that Cn = 1 is superfluous; for in this case, we may, if necessary, multiply g by cn- l and thus reduce the leading coefficient to 1. Exercise 3.12. If x, y, ... are an infinite number of symbols, we may consider the totality of all 9t-polynomials in these indeterminates. Every polynomial, however,

Ideals. Residue Class Rings

47

must contain only a finite number of these indeterminates. Prove that the domain thus defined is, respectively, a ring or integral domain whenever 9t is a ring or integral domain.

3.5 IDEALS.

RESIDUE CLASS RINGS

Let 0 be a ring. For a subset of 0 to be itself a ring (subring of 0), it is necessary and sufficient

1. That the subset be a subgroup of the additive group; in other words, that it contain with a and b, also a-b (module property); 2. That it contain, with a and b, also a· b. Some of the subrings, which we shall call ideals, playa special role, in analogy to the normal divisors in group theory. A nonempty subset m of 0 is called an ideal, or better a right ideal if 1. a Em and b Em imply a-b

Em

(module property); 0 (in words: the module m shall contain all "right multiples" a· r for every a).

2. a Em implies ar Em for an arbitrary r in Similarly, a module is called a left ideal if a

in

E

m implies ra Em for an arbitrary r

o.

Finally, m is called a two-sided ideal ifm is both a left and a right ideal. For commutative rings th~ three concepts coincide, and we speak simply of ideals. In this section we shall further assume that 0 is a commutative ring. Ideals will always be denoted by small German letters. Examples of ideals:

1. The null ideal, consisting of the zero element alone. 2. The unit ideal 0, including ~ll elements of the ring. 3. The ideal (a) generated by an element a; it consists of all expressions of the form (r E 0, n is an integer). ra+na

It is easily seen that this set is always an ideal: the difference of two such expres.. sions is obviously of the same form, and an arbitrary multiple is of the form s·(ra+na) = (sr+ns)·a.

The ideal (a), evidently, is the smallest ideal containing a: for every such ideal = na, hence all sums has to contain at least all multiples ra and all sums ± ra+na. Therefore the ideal (a) may also be defined as the intersection of all ideals containing a as an element. If the ring 0 has the identity e, we may write ra+nea = (r+ne)a = ,'a instead of ra+na; in this case (a) thus consists of all ordinary multiples rae For example, the ideal (2) in the ring of integers consists of all even integers.

La

48

RINGS AND FIELDS

An ideal (a) generated by an element a is called a principal ideal. The null ideal (0) is always a principal ideal, and so is the unit ideal 0, provided 0 contains an identity e; then 0 = (e). In noncommutative rings we must distingiJish between left and right principal ideals. The right principal ideal generated by a consists of all sums or + no. 4. Similarly, the ideal generated by several elements a1, ••. , an may be defined as the totality of all sums of the form

L 'Il,+ L nfJJ (or, if 0 contains an identity, as L r,a,), or as the intersection of all ideals of o containing the elements aI' ... , an. The ideal is denoted by (a 1, ••• , an), and an are said to form an ideal basis. In a similar manner we can define the ideal (IDl) generated· by an infinite set U; it is the totality of all finite sums of the form

a l'

to

••

,

s.

L riaj + L nfl

(a

j

E

IDl, rj E 0, nJ are integers).

RESIDUE CLASSES An ideal m in 0, being a subgroup of the additive group, defines a partition of 0 into cosets or residue classes modulo m. Two elements a, b are called congruent modulo m, if they belong to the same residue class, that is, if a-b Em. In symbols: a = b(modm) or briefly a = b(m). For "a noncongruent to b" we write a :$ b. If, in particular, m is a principal ideal (m), we should write a == b«m» instead of a == b(m). However, in this case we omit one pair of parentheses and simply write a = b(m). In this way we may arrive, for example, at the ordinary congruence modulo an integer a == b(n) (in words: a is congruent to b modulo n) means a-b belongs • to (n), that is, a - b is a multiple of n.

CALCULATIONS WITH CONGRUENCES The validity of a congruence a = b modulo an ideal m is obviously preserved when the same element c is added to both sides, or when both sides are multiplied by c. From this we infer: If a == a' and b = b', then °a+b ab

=a+b' == a' +b'

=00' =a'b'.

Thus congruences may be added to and multiplied by one another. We may likewise mUltiply both sides of a congruence by an ordinary integer n.

Ideals. Residue Class Rings

49

By taking n = - 1, we infer that congruences may be subtracted from each other. Thus we may perform the same operations with congruences as we do with equations; however, in general, we are not permitted to divide; for example, in the domain of integers we have 15

== 3(6);

but although 3 $ 0(6), we cannot infer that 5

=1(6).

Exercises 3.13.

Show that in the ring of integers the residue classes modulo an ideal (m) (m>O) may be represented by the numbers 0, I, ... ,m-I and may thus be denoted by .Ro, .Sl1' · • • , .R"._ 13.14. What ideal is generated by the numbers 10 and 13 together in the ring of integers? 3.15. What does a == b(O) mean? 3.16. All multiples ra of an element a form an ideal oa. Considering the ring of the even integers, make clear to yourself that this ideal is not necessarily identical with the principal ideal (a). Ideals bear the same relation to ring homomorphism as do norma] subgroups to group homomorphism. Let us start from the notion of homomorphism. A homomorphism 0 "......, 0 between two rings defines a partition of the ring 0: a class 5\" is formed by all elements a having the same image a. We can characterize these classes more precisely, as follows. The class n of 0 to which corresponds the zero element under the homomorphism o ".. . ., 0 is an ideal in 0, and the other classes are the residue classes of this ideal. Proof: In the first place n is a module, for if a and b become zero under the homomorphism, so does -b, and hence also the difference a-b; thus, if a and b belong to the class n, so does a-b. Also, n is an ideal, for if a is mapped into zero, and if r is arbitrary, ra is mapped into f-O = 0, thus belonging to n again. n is thus a two-sided ideal in o. The elements a + c(C En) of a residue class modulo n with a as its representative are carried into ti + 0, hence into d; therefore, all of them belong to a class 5\a. If, conversely, an element b is carried into a, then b-a becomes a-a = 0; hence b - a E n, and b lies in the same residue class as Q. This completes the proof. Thus, to every homomorphism belongs an ideal. And now for the converse. We start from an ideal m in 0 and ask whether there exists a ring 0 homomorphic with 0, so that the elements of ij correspond exactly to the residue classes modulo m. In order to construct such a ring, we proceed in the same ~anner as we did

so

RINGS AND FIELDS

in Section 2.5: As elements of the ring to be constructed we simply choose the residue classes modulo m, denote the residue classes a+m by a, and try to define for them an addition and multiplication so that the correspondence a~d constitutes a homomorphism. Thus, for any two residue classes a, h, we have to determine a sum class Ii + b and a product class Ii· b so that all the sums of the elements of d and those of h are in the sum class and all products in the product class. Thus let a be an element in ti, and b one in b. We tentatively define d + b as the class containing a+b, and a" b as the class containing a·b. If a' a is some other element of a, and b ' = b one of b, then, according to the above, 8

=

a'+b'

=a+b

a'·b'

= a'b;

hence a' +b' is in the same residue class as a+b, and a' ·b' in the same as a-b. Our definition of the sum class and product class is therefore independent of the choice of the elements a, b within a, h. Now these classes a+ h, a· b have the desired property, namely that every sum a' +b' is in the sum class d+ h, and that every product a'· b' is in the product class of a' h. To every element a there corresponds a residue class d; this correspondence is a homomorphism, since the sum a+b corresponds to the sum a+b, and the product dh likewise to abo Hence the residue classes form a ring (Section 3.2). We shall call this ring the residue class ring o/m of 0 modulo m. The ring 0 is homomorphically mapped upon o/m by means of the correspondence mentioned before. For this homomorphism the ideal m plays the same role as n above; it is indeed identical with the set of all elements whose residue class is the zero class. We note the fundamental importance of the ideals: they enable us to con,struct rings homomorphic with a given ring. The elements of such a new ring are the residue classes modulo an ideal: with every element a there is associated a residue class d. Two residue classes are added or multiplied by adding or multiplying any two representatives of these residue classes. Since a = b implies d = b, the transition to the residue class ring transforms congruences into equalities. The special rings homomorphic with 0, as here constructed, that is, the residue class rings o/m, essentially exhaust all rings homomorphic with o. For if 0 is an arbitrary homomorphic image of 0, there is, as we have seen, a biunique correspondence between the elements' 'of 0 and the residue classes of 0 modulo an ideal n in o. The element d in i.i corresponds to the residue class .Ra • The sum and the product of two residue classes .Ra , .Rb are given by .Ra + band .Rab , respectively, and to the latter correspond, respectively, the elements

a+b

= a+b

and ab = 8All

congruences are of course modulo m.

dh.

Divisibility. Prime/deals

51

Hence the correspondence of the residue classes to the elements of D constitutes an isomorphism. Thus we have proved the following. Any ring 0 homomorphic with 0 is isomorphic with a residue class ring o/n, where n is the ideal of those elements whose image in '0 is the zero. Conversely, every residue class ring o/n is a homomorphic image 0/0. (Homomorphism theorem lor rings). EXAMPLES OF A RESIDUE CLASS RING In the ring of integers we may denote the residue classes modulo a positive number m by Ro, R l' ••. , .R m - 1 (cf. Exercise 3.13), where .R" consists of those numbers which, upon division by m, leave a remainder a. In order to add or multiply two residue classes R 5l: b , we add or multiply their representatives a, b, and reduce the result to its least nonnegative remainder modulo m. Q ,

Exercises 3.17. The residue class ring olm may have divisors of zero, even though 0 does not have any. Give examples in the ring of integers. 3.18. The homomorphism 0 0 is an isomorphism if and only if n = (0). 3.19. In a field there are no ideals except for the null ideal and the unit ideal. Furnish the proof. What does this imply for the possible homomorphic mappings of a field? f'J

3.6 DIVISmILITY. PRIME IDEALS

:Let b be an ideal (or, more generally, a

module) in the ring o. If a is an element ofb, we may write a O(b), and we say that a is divisible by the ideal' b. If all the elements of an ideal (or of a module) Q are divisible by b, then a is called divisible by b; this simply means that a is a subset ofb. In symbols:

=

a = O(b). We call Q a multiple or, in modern terminology, a subideal ofb. Similarly, b is called a divisor or an overideal of Q. If moreover Q =f= b, then b is called a proper divisor of Q and Q is called a proper multiple of b. For principal ideals in commutative rings with identity, (a) = simply means a = rb, and the concept of divisibility as defined by ideals becomes identical with the ordinary concept. From now on all rings under consideration will again be commutative. An i<:ieall' in 0 is ca'lled a prime ideal if its residue class ring o/p is an integral domain, that is, one which has no divisors of zero. If we denote residue classes modulo p by bars, as we did before, this condition means that and d =F 0 implies b = 0

O«b»

S2 Of,

RINGS AND FIELDS

what amounts to the same thing,

ab

= O(p)

and a =1= O(V) Implies b

== O(p)

for arbitrary a and b in o. In words: A product shall be divisible by the ideal p, only if one factor is divisible by it. It is clear that the unit ideal is alway~ prime, for the condition a =1= 0(0) can never be satisfied. The zero ideal is a prime ideal if and only if the ring 0 itself is an integral domain. Further examples of prime ideals are the principal ideals generated by the prime numbers in the ring l of integers, as we shall see later. An ideal in 0 is called maximal if it is not included in any other ideal in 0 ezcept in 0 itself, or in other words, if it has no proper divisors except the unit idaU o. For example, the prime principal ideals (P) in l just mentioned are maximal. Let 0 be a ring with identity element. Any maximal ideal p in 0, different from D itself, is a prime ideal, and the residue class ring o/p is a field. If, conversely, o/p is a field, then p is maximal. Proof: Let us solve the equation xa == h in the residue class ring for d =1= 0, ~upposing a =1= O(p). P and a together generate an ideal which is a divisor of p and (since it contains a) even a proper divisor ofp; hence it must be equal to o. Therefore, any arbitrary element b of 0 may be written in the form

b == p+ra

(p E:P, rEo).

By virtue of the homomorphism of 0 with the residue class ring, it follows that

h == fa, which solves the equation xli == h. Thus it is seen that the residue class ring is a field. Since a field does not have any zero divisors, the ideal p is a prime ideal. If, conversely,o/p is afield, a a proper divisor ofp, and a an element of a not belonging to p, then the congruence ax is solvable for every b in

= b(p)

o. It follows that ax

=b(a)

o =b(a);

hence (l = 0, since b may be any element of o. Not every prime ideal is maximal. This may be seen from the example of the null ideal in the ring of integers or, less trivially, by the ideal (x) in the integral polynomial domain l[x] which has among others the ideal (2, x) as a proper divisor. Both (x) and (2, x) are prime ideals, as can be verified easHy.

Euclidean Rings and Principal Ideal Rings

53

Exercises 3.20. Prove this last assertion. '3.21. Discuss the properties of the residue class rings of the ideals (2) and (3) in the ring of integers, and prove that these ideals are prime.

G.e.D. AND L.e.M. The ideal (a, b) generated by the union of two ideals Q and b is also known as the greatest common divisor (g.c.d.) of these ideals, since it is a common divisor which is divisible by every common divisor. It is also known as the sum of the two ideals, because it evidently consists of ail sums a + b where a E 4, b E b. Similarly, the intersection Q (') b of two ideals Q, b is known as their least common multiple (I.c.m.), because it is a common multiple, and because every other multiple is divisible by it.

3.7 EUCLIDEAN RINGS AND PRINCIPAL IDEAL RINGS Theorem: In the ring l. of integers every ideal is a principal ideal. Proof: Let a be an ideal in Z. H Q = (0), the proof is completed. If Q contains a number c =t= 0, it also contains - c, and one of these numbers is positive. Let a be the least positive number in the ideal

Q.

If b is an arbitrary number in the ideal, and if r is the remainder left in the division of b by a, then

b = qa+r,

O
Since b and a belong to the ideal, b-qa = r belongs to it as well. Since r
b = qa+r. If r =t= 0, the degree of r is less than that of a, and so on. An integral domain with identity in which every ideal is principal is called a prinCipal ideal ring. As has just been proved, the ring l of integers, as well as every polynomial ring p[x], is a principal ideal ring. In a trivial fashion, every field is, furthermore, a principal ideal ring. For if an

,

54

RINGS AND FIELDS

ideal a. in the field P is not the null ideal, it contains a- 1a = 1 for an arbitrary Q =F 0; hence Q = (1) is the only ideal besides the null ideal. (Cr. Exercise 3.19.) The reasoning just applied in two cases may be generalized as follows: Let 91 be a commutative ring in which for every ring element a distinct from zero a nonnegative integer g(a) is defined so that

1. For a =F 0 and b =+ 0, ab :1= 0 and

g(ab)~g(a);

2. (Division algorithm) For any two ring elements exists an expression b = qa+r

Q,

b, where a =1= 0, there

= 0 or g(r)
in which either r

For 9t = Z for 9{ = P[x] the degree of the polynomial a is g(a). A ring with the properties mentioned is called a Euclidean ring. By means of the reasoning that was previously applied in the two cases 91 = Z and 9t = P[x], we can now derive the following theorem. Deorem: In a Euclidean ring every ideal is principal, and all elements of the ideal are multiples qa of the generating element a. Applying this theorem to the unit ideal in particular, that is, the entire ring, we see that there exists an a such that all ring elements are multiples qa of it. In particular, a itself is expressible thus:

a = ae. For b

= qa it follows that qa == qae;

hence b == be.

Thus we have proved the following. A Euclidean ring always possesses an identity element. Two elements a, b of a Euclidean ring which are distinct from zero generate an ideal (a, b) consisting of all expressions of the form ra+sb. This ideal is principal, that is, it is generated by an element d. Thus we have d

= ra+sb,

a =gd

b = hd.

(3.10) (3.11)

By (3.11), d is a common divisor of a and b. By (3.10), d is also the greatest common divisor; that is, all common divisors of a and b are divisors of d. Thus we may state the following theorem. Theorem: In a principal ideal ring any two elements a, b have a greatest common divisor d expressible in the/orm (3.10). The greatest common divisor is usually designated by d == (a, b). A more exact notation, however, would be (d) == (a, b), for it is only the ideal (d) and not the element dthat is uniquely determined by a and b. If(a, b) = 1, then a and b are called relatively prime.

Euclidean Rings and Principal Ideal Rings

SS

The above existence proof for the g.e.d. does not provide a tool for actually computing it. For Euclidean rings there is such a method, consisting in successive divisions (the Euclidean algorithm after which Euclidean rings are named), which was given by Euclid. 9 Let two ring elements ao, a 1 be given, and let g(a 1) ~ g(ao}. Then, by the division algorithm, we let

ao = qla 1 +a2

g(a2)
aJ: = q2 a 2+ a 3

g(a3}
and continue in this way, until some division yields the remainder 0: a,-1 = qsDs·

Then all nUmbers ao, ai' a2, - - . , as are of the form rao + sa 1- Every divisor of as (and, in particular, as itself) is, according to the last equation, also a divisor of a.-I, furthermore a divisor of QII_ 2, and finally of a 1 and ao. Hence, all is the greatest common divisor of ao and aiThese considerations may also be applied to the noncommutative case, provided there exist a left-sided and a right-sided division algorithm:

b = qla+rl = aq2+ r 2,

g(rt)
g(r2)
It follows that every left ideal contains an element a such that all elements of the ideal are left multiples qa of a, and that likewise every right ideal contains an element a such that all elements of the ideal are right mUltiples aq of a. A twosided ideal possesses a generating element a such that all elements are both right and left multiples of Q. Applying "this to the unit ideal, it follows that there exist a left and a right identity; that is,~ that there is an identity element. Finally, we may prove, as above, the existence of a left-sided as well as of a right-sided g.e.d. of two elements a, b_ The most important example of a noneommutative Euclidean ring is the polynomial ring P[x] over a skew field P.

Exercises 3.22. The relation (a, b) = d remains valid when the ring 0 is extended to any larger ring o. 3.23. Every element a of order r· s in a group (fj is the product of a uniquely determined element tt' of order s and a uniquely determined element au of order r, provided the numbers rand s are relatiyely prime: (r, s)

= 1.

3.24. A cyclic group of order n with the generating element a can also be generated by any power ~,/provided (p" n) = 1. 9Euclid, Elements, Book 7, Theorems 1 and 2.

56

lUNGS AND FIELDS

ANOTHER EXAMPLE OF A EUCLIDEAN RING The complex numbers a+bi (a and b are ordinary integers) form the ring of Gaussian integers. From the definition of a product

= (ac-bd)+(ad+bc)i, "norm" of a number ex = a+bi by N(rx) = (a+bi) (a-bi) = a2 +b2 , (a+hi) (c+di)

on defining the

we easily derive the equation

N(rxP)

= N(ex)· N(f3).

(3.12)

The norm N(rx) is an ordinary integer which, being the sum of two squares, YaDishes only when rx vanishes, and which is positive in any other case. From (3.12) it follows that a product rxp vanishes only when« or p vanishes; hence the ring is an integral domain. According to Section 3.3, a quotient field exists. If ex = a + bi =f= 0, then /X-I

=

a-bi N(/X);

thus the numbers of the quotient field may be expressed by (a/n) + (b/n}i (a, b, n are integers). These "fractional numbers" form the "Gaussian number field."

The definition of the norm and equation (3.12) hold for the elements of this field

as well. In order to arrive at a division algorithm for the ring of the Gaussian integers, we have to find for a given ex and P =* 0 a number« -'AP having nonn less than {J. Let us first determine a fractional number 'A' = a' +b'i so that a.-'A'p = 0; then let us replace a' and b' by the nearest integers a and b, and put 'A = a+bi, 'A' -'A = B. Then we have rx - AfJ = «- 'A'(J + BfJ = efJ N( rx - >tfJ) = N(e)N(fJ) N(B) = N(>"'->-') = (a'-a)2+(b'-b)2 ~ N(a. - >13) < N(ft).

(t)2+(l)2<1

Thus we have found a "division algorithm," which proves that the ring is a Euclidean ring. to note: Concerning the question whether the Euclidean algorithm or its generalization exists in pbitrary principal ideal rings, see H. Hasse in J. reine u. angew. Math., 159, 3-12 (1928). Investigations as to the question in what algebraic number rings the Euclidean algorithm is valid were carried out by o. Perron (Math. Ann., Vol. 107, p. 489), A. Oppenheim (Math. Ann., Vol. 109, p. 349), E. Berg (Kgl. Fysiogr. Siillskapets Lund Fiirhandl. Vol. SN S), N. Hofreiter (Mh. Math. Physik, Vol. 42, p. 397), H. Behrbohm and L. Redei (J. reine u. angew. Math., Vol. 174, p. 198). 10Bibliographic

Factorization

57

3.8 FACtORIZATION In this section we shall be concerned solely with integral domains containing an identity. Let us first investigate what we mean by prime elements or indecomposable elements in these domains. We shall consider only ring elements distinct from zero, even when this is not expressly stated. A prime number in the ring of integers may always be decomposed into factors, even in two ways:

p

= p·l = (- p). ( -1).

However, one of these factors is always a "unit", that is, a number 8, whose inverse 8- 1 is likewise in the ring; + 1 and -1 are units. 1f, in general, an integral domain with identity is given, then by a unit 1 ! we understand an element 8 which possesses an inverse e - 1 in the domain. Then e - 1, obviously, is also a unit. If 8 is a unit, then every element a admits a factorization

Such factorizations where one factor is a unit may be called trivialfactorizations. An element p =t= 0 which admits only trivial factorizations of the kind p = ab, where a or b is a unit, is called an indecomposable element or a prime element. (In case of integers we say: prime number; in case of polynomials: irreducible polynomial. ) Two quantities, such as a and b = as - 1, which differ only by a unit as factor, are sometimes called associates. Either one is a divisor of its associate, and for their respective principal ideals we have (a) c (b),

(b) c (a),

hence (b) = (a).

Thus two associates "generate the same principal ideal. If, conversely, either of the two quantities a and b divides the other one, namely,

a = be,

b = ad,

it follows that

b = bcd,

hence

1 = ed,

hence e and d are units, and a and b are associates. If c is a divisor of a, but not an associate of a, that is, a

= ed, and d is not

a

11 The word "unit" is often used as a synonym for "unit element." However, these concepts are to be clearly distinguished in discussing factorization, since, for example, - 1 is also a unit.

58

RINGS AND FIlLDS

unit, then c is called a proper divisor of Q. In this case a is not a divisor of c, and the ideal (e) is a proper divisor of the ideal (a). For if a were a divisor of c, say c = 00, then we would have

L

a=cd==abd 1 = bd

and d would be a unit, contrary to our assumption. A prime element may also be defined as an element distinct from zero which does not possess any proper divisors except units. 'I1Ieorem: If, in a Euclidean ring, b is a proper divisor of a, then g(b)
b == aq+r,

g(r)
Equating a == be, it follows that

r = b-aq = b(l-cq)

g(r)

~ g(b);

hence g(b)

~

g(r)
In a Euclidean ring every element a distinct from zero is a product of prime elements:

a == P1P2 .•• p,.

Remark: More generally, the theorem can be proved for principal ideal rings, but we must then use the axiom of choice (Section 9.2). This part of the book is intended to be elementary, and thus the axiom choice will not be employed. The proof is therefore given only for Euclidean rings. Proof: We apply the method of induction, on g(a): Let the assertion be true. for all elements b with g(b)
g(c)
By the induction hypothesis, band c are products of prime elements. Hence a = bc is also a product of prime elements. We now investigate the uniqueness of factorization into primes a = P IP2 • • • p, and consider not only Euclidean rings, but arbitrary principal ideal rings.

In a principal ideal ring a prime element, other than Q unit, generates a maximal prime ideal (whose residue closs ring is thus afield). Proof: If p is prime, then it has no proper divisors except units, and therefore (since every ideal is a principal ideal) the ideal (P) has no proper ideal divisors except the unit ideal. Remark: The solvability of the equation ax == b in the residue class ring or

....

Factorization

59

of the congruence ax = b(p) in the given ring may, of course, readily be seen from the fact that, for a =1= O(p), we have (a, p) = 1. For this implies

1 = ar+ps b = arb+psb b = arb(p). We infer at once: If a product is divisible by the prime element p, so is one o/the factors; for the residue class ring has no divisors of zero.

Exercises 3.25. Solve the congruence 6x

= 7(19)

using the Euclidean algorithm. 3.26. If in a principal ideal ring a product ab is divisible by c and a is not divisible by c, then b is divisible by c. We are now in a position to prove the theorem o/uniqueness o!prime!actoriza-

tion in principal ideal rings. Let a

= PIP2 · • · Pr = qlq2 .•. q.

(3.12)

be two factorizations of the same number a in a principal ideal ring. We shall exclude the trivial case where a is a unit and where, consequently, all Pi and q} are units. Then we may assume that P 1 and q 1 are not units, and that all possible units among the factors Pi and qj are combined with the factor PI and Ql, respectively. Thus let the PI and qj not be units. Now we state: r = s, and the Pi and qj are identical, except/or their order and/or unit/actors. For r = 1 the proof is clear, for since a = Pi is prime, the product ql • • • qs can .contain only one factor q I = PI- Thus we may proceed by induction on r. SincePI divides the productql _. _q.,PI must divide one of the factorsqi. With the q rearranged, PI will divide q I : (3.13) Here el must be a unit, or else ql would not be prime. Substituting (3.13) in (3.12) and dividing by P1' we obtain

'P2 · • •Pr

= (s1Q2)q3 · · · q..

(3.14)

By the induction hypothesis, the factors on the left and right side of (3.14) must be the same, except for the unit factors. Since PI is identical with ql' except for the unit factor e 1, the proof is completed. From the theorems proved we infer: The elements 0/ a Euclidean ring are uniquely expressible as prQducts of prime elements, except for units and for the

60

RINGS AND PIELDS

order of the/actors. This is true in particular for the integers, for the polynomials in one variable with coefficients from a field, and for the Gaussian integers.

Exercises

3.27. The integral polynomialsf(x) modulo any prime number p are uniquely decomposable into factors which are irreducible modulo p. 3.28. What are the units of the Gaussian number ring? Decompose into prime factors the numbers 2, 3, S in this ring. 3.29. For the number 4 in the ring of the numbers a+bR there are two substantially different factorizations into prime factors:

4

=

2·2

=

(I+N> (l-N>·

3.30. Iil a principal ideal ring the residue classes modulo a consisting of elements relatively prime to a form. a group under multiplication.

In Chapter S we shall see that there are rings other than principal ideal rings for which the unique factorization theorem holds., For all such rings we shall now prove the following theorem.

'I1aeorem: If in 0 every element factors uniquely into prime elements, then every prime element p generates a prime ideal, and every nonprime element distinct from zero generates a nonprime ideal. Proof: Let p be prime. If ab == O(p), then the factor p must occur, when ab is factored. This factorization, however, is obtained by combining the factorizations of a and b; therefore, the factor p must already occur in a or b, whence a = O(p) or b - O(p). Now let p factor: p = ab, where a and b are proper divisors of p. Then it follows that ab == O(p), a =$ O(p), b =$ O(p). Therefore the ideal (P) is not prime.

Exerdse

3.31. Prove that for all rings with unique factorimtion every two or more elements have a "greatest common divisor" and a "least common multiple," both of them being determined except for unit factors.

Remark: For rings of the kind considered, the g.e.d. in the sense of an element is not always the same as the g.c.d. in the sense of an ideal. For example, in the polynomial domain of a variable x with integer coefficients the elements 2 .nd x have no common divisors except units; but the ideal (2, x) is not the unit ideal. (In Chapter 5 it will be proved thai there is unique factorization in this ring.)

.Chapter 4 VECTOR SPACES AND TENSOR SPACES

4.1 VECfOR SPACES Let (1) K be a skew field with elements a, b, ... which are called coefficients or scalars, (2)!R be a module (that is, an additive Abelian group) with elements x, y, ... which are called vectors, and (3) xa be a multiplication of vectors with scalars with the following properties: VI. xa lies in IDl. V2. (x+l)a = :ra+ya. V3. x(a+b) = xa+xb. V4. x(ab) = (xa)b. VS. xl = x. If these requirements are fulfilled, then IDl is called a vector space over K or, more precisely, a right K vector space, since the coefficients a stand to the right of the vectors. The concept of a left K vector space is defined analogously; the associative law V4 for a left vector space reads V4* (ab)x = ~b%). If K is commutative, we may also write %a in place of ax. A right vector space thus becomes a left vector space. If, however, K is not coD\mutative, then we must distinguish between right and left vector spaces. We write xab rather than x(ab) or (xa)b. The zero element ofrol is denoted by ojust as the zero element for K. Examples of vector spaces are all extension fields of a field K and, more generally, of all rings R containing a skew field K as long as the unit element of K is also a unit element of R. From V2 it follows as usual that (Xl + · · · +x,)a = %la+ ... +x,a (x-y)a = xa-ya O·a = O. 61

62

VECTOR SPACES AND TENSOR SPACES

In the same way, it follows from V3 that

x(a1 +

· · · +a,) = xal + · · · +xa. x(a-b) = xa-xb x·O = O.

The vector space 9R is called finite dimensional or finite if there are finitely many generators Sl, ••• e", in terms of which any element ofIDl can be expressed with coefficients d' from K: 1

(4.1) If one of the generators e" can be expressed in terms of the other eb then this s" is redundant as a generating element of IDl. If we delete this element from the sequence el" •. ,em and continue in this manner until there are no more redundant elements ~ b then n basis vectors PI' . . . ,p,. remain, no one of which can be expressed as a linear combination of the others. Such vectors, no one of which can be expressed as a linear combination of the remaining vectors, are called linearly independent. H JJ l ' ••• , p,. are linearly independent, then pla l + · · · +p"ti' = 0 (4.2)

implies a1

0, ... , d'

= O.

Indeed, if one of the a f =t= 0, then" in (4.2) can be expressed in terms of the other vectors. If Pl' ... ,p" form a linearly independent basis for the vector space m, then any vector x can be expressed uniquely in terms of the p" with coefficients ~ fromK: (4.3) x = Lp"xi. For if there is another such expression for the same vector x,

x

= LP"y",

(4.4)

then by subtracting (4.4) from (4.3) a linear dependency

L p.Jxi - 1') = 0 is obtained; hence all the differences xi-y" are zero, and xi is equal to yk for all k. From (4.3) it follows that to each vector x there corresponds a unique sequence of coefficients Xl, ••• , X' from K which we call the coordinates of the vector x lIn denoting the coefficients t:i' with upper indices, we are followina a convention introduced by Einstein which is convenient in the vector and tensor calculus. According to this convention, a repeated index occurring once as an upper index and once as a lower index

implies summation.

~

Vector Spaces

63

with respect to the basisPl' ... ,JI,.. Conversely, to each sequence orn coefficients of Kthere corresponds, according to (4.3), a unique vector x. For a fixed basis there is thus a one-to-one correspondence (4.5) vectors may be added by adding their coordinates:

A vector may be multiplied by a by multiplying its coordinates by a:

xa = (LI'"x1')a = LPI;(xka). The number n of the basis vectors is called the dimension of the vector space In Section 4.2 we shall see that the dimension is independent of the choice of basis. A vector space of dimension n which may serve as a model for all vector spaces of the same dimension can be obtained in the following manner. A vector x is defined to be a sequence of n elements Xl, ••• , X' of K. The sum of two vectors x and y is defined as the n-tuple (x 1 +Y 1 , ••• , ~ +y"). A vector x is multiplied by a by multiplying the individual xl by Q. The addition and multiplication thus defined meet all the conditions defining a vector space. The n vectors

m.

(1 at

e" = (0, . . . , 1, 0, . . . , 0) form a basis, since any vector x

th~

kth place)

= (Xl, • •• ,x") can be uniquely represented as

Our model vector space thus does indeed have dimension n. From correspondence (4.5) we have the following.

Every vector space of dimension n over K is isomorphic to the model vector space consisting of n-tuples (Xl, . • . , x"). Exercise 4.1. If we go over from' one basis P l' ••• ,1',. to another basis e 1, ... '. ,en of the same vector space and if the old basis elements PI; are expressed in terms of the new basis elements e, with coefficients Pi i:

Pk = then the new coordinates coordinates by

'Xl of a

LeUJ,,',

vector x are expressed in terms of the old

64

VBCI'OR. SPACES AND TENSOR. SPACES

4.2 DIMENSIONAL INVARIANCE We wish to prove that the dimension of a vector space IDl, that is, the number of elements in a linearly independent basis, is independent of the particular choice of basis. An elementy is called linearly dependent on Xl, ••• , x". (with respect to K) if

1 = x 1a 1 +

...

(4.6)

+%"",'"

or, what amounts to the same thing, if the linear relation

yb+x 1b 1 +

· · · +x,JJrn =

0

(4.7)

obtains with b =t= O. In particular,1 is said to be dependent on the empty set if y = o. There are a number of theorems concerning linear dependence which will be presented as main theorems and corollaries. The main theorems will be deduced directly from the definition of the concept. The corollaries, on the other hand, will be derived from the main theorems without further use of the definition, that is, without direct reference to the concept of "linear dependence." This procedure is useful in regard to a later chapter which will introduce the concept of "algebraic dependence," for which the same main theorems and thus also the corollaries are valid. Three main theorems are sufficient. The first one is obvious. MaIn Theorem 1: Every Xi is linearly dependent on Xl' ••• , X •• Main Theorem 2: Ify is linearly dependent on Xl' ••• , X'" but not on Xl' ••• , X 111- l' then X... is linearly dependent on Xl, • • • , x"._ l'y. Proof: In equation (4.7), bfll ::f: 0, for otherwise y would be dependent only on % 1, • • • , %.,.-1-

Main Theorem 3: If z is linearly dependent on Y1' .. · ,y" and if each 1 j is linearly dependent on XI' ••• , x"., then z is linearly dependent on Xl' ••• , x .... Proof: From z = Ly"rf andy" = L xp,,' it follows that

z=L