Abstract Algebra Theory and Practice
Abstract Algebra Theory and Practice
Abstract Algebra Theory and Practice
Abstract Algebra
Theory and Applications
Thomas W. Judson
Stephen F. Austin State University
19972015
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License,
Version 1.2 or any later version published by the Free Software
Foundation; with no Invariant Sections, no Front-Cover Texts, and
no Back-Cover Texts. A copy of the license is included in the appendix entitled GNU Free Documentation License.
Acknowledgements
Preface
vii
dependency chart appears below. (A broken line indicates a partial
dependency.)
Chapters 16
Chapter 8
Chapter 9
Chapter 7
Chapter 10
Chapter 11
Chapter 13
Chapter 16
Chapter 12
Chapter 17
Chapter 18
Chapter 20
Chapter 14
Chapter 15
Chapter 19
Chapter 21
Chapter 22
Chapter 23
Though there are no specific prerequisites for a course in abstract algebra, students who have had other higher-level courses in
mathematics will generally be more prepared than those who have
not, because they will possess a bit more mathematical sophistication. Occasionally, we shall assume some basic linear algebra;
that is, we shall take for granted an elementary knowledge of matrices and determinants. This should present no great problem,
since most students taking a course in abstract algebra have been
introduced to matrices and determinants elsewhere in their career,
if they have not already taken a sophomore or junior-level course
in linear algebra.
Exercise sections are the heart of any mathematics text. An
exercise set appears at the end of each chapter. The nature of the
exercises ranges over several categories; computational, conceptual,
and theoretical problems are included. A section presenting hints
and solutions to many of the exercises appears at the end of the
text. Often in the solutions a proof is only sketched, and it is up to
the student to provide the details. The exercises range in difficulty
viii
from very easy to very challenging. Many of the more substantial
problems require careful thought, so the student should not be
discouraged if the solution is not forthcoming after a few minutes
of work.
There are additional exercises or computer projects at the ends
of many of the chapters. The computer projects usually require a
knowledge of programming. All of these exercises and projects are
more substantial in nature and allow the exploration of new results
and theory.
Sage (sagemath.org) is a free, open source, software system for
advanced mathematics, which is ideal for assisting with a study of
abstract algebra. Sage can be used either on your own computer, a
local server, or on SageMathCloud (https://cloud.sagemath.com).
Robert Beezer has written a comprehensive introduction to Sage
and a selection of relevant exercises that appear at the end of each
chapter, including live Sage cells in the web version of the book.
The Sage code has been tested for accuracy with the most recent
version available at this time: Sage Version 6.8 (released 2015-0726).
Thomas W. Judson
Nacogdoches, Texas 2015
Contents
Acknowledgements
Preface
vi
1 Preliminaries
1.1 A Short Note on Proofs . . . . . .
1.2 Sets and Equivalence Relations . .
1.3 Exercises . . . . . . . . . . . . . .
1.4 References and Suggested Readings
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
4
16
19
2 The
2.1
2.2
2.3
2.4
2.5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21
21
24
29
32
33
3 Groups
3.1 Integer Equivalence Classes and Symmetries
3.2 Definitions and Examples . . . . . . . . . .
3.3 Subgroups . . . . . . . . . . . . . . . . . . .
3.4 Exercises . . . . . . . . . . . . . . . . . . .
3.5 Additional Exercises: Detecting Errors . . .
3.6 References and Suggested Readings . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
34
34
39
45
48
52
54
.
.
.
.
.
.
55
55
59
63
65
69
69
Integers
Mathematical Induction . . . . . .
The Division Algorithm . . . . . .
Exercises . . . . . . . . . . . . . .
Programming Exercises . . . . . .
References and Suggested Readings
4 Cyclic Groups
4.1 Cyclic Subgroups . . . . . . . . . . . . . . .
4.2 Multiplicative Group of Complex Numbers
4.3 The Method of Repeated Squares . . . . . .
4.4 Exercises . . . . . . . . . . . . . . . . . . .
4.5 Programming Exercises . . . . . . . . . . .
4.6 References and Suggested Readings . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 Permutation Groups
71
5.1 Definitions and Notation . . . . . . . . . . . . . . . . 71
5.2 Dihedral Groups . . . . . . . . . . . . . . . . . . . . 79
5.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . 83
ix
CONTENTS
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
87
87
89
91
93
7 Introduction to Cryptography
7.1 Private Key Cryptography . . . . . . . . . . .
7.2 Public Key Cryptography . . . . . . . . . . .
7.3 Exercises . . . . . . . . . . . . . . . . . . . .
7.4 Additional Exercises: Primality and Factoring
7.5 References and Suggested Readings . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
95
96
98
102
104
105
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
107
107
115
119
125
128
133
134
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9 Isomorphisms
9.1 Definition and Examples . . . . . . . . . . . . . . .
9.2 Direct Products . . . . . . . . . . . . . . . . . . . .
9.3 Exercises . . . . . . . . . . . . . . . . . . . . . . .
135
. 135
. 140
. 144
149
. 149
. 152
. 155
11 Homomorphisms
11.1 Group Homomorphisms . . . . . . . .
11.2 The Isomorphism Theorems . . . . . .
11.3 Exercises . . . . . . . . . . . . . . . .
11.4 Additional Exercises: Automorphisms
.
.
.
.
.
.
.
.
.
.
.
.
168
. 168
. 176
. 183
. 185
.
.
.
.
187
. 187
. 191
. 195
. 197
Structure of Groups
Finite Abelian Groups .
Solvable Groups . . . .
Exercises . . . . . . . .
Programming Exercises
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
158
158
161
164
166
CONTENTS
xi
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
198
198
201
203
211
214
214
Sylow Theorems
The Sylow Theorems . . . . . . . .
Examples and Applications . . . .
Exercises . . . . . . . . . . . . . .
A Project . . . . . . . . . . . . . .
References and Suggested Readings
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
215
. 215
. 219
. 223
. 225
. 225
16 Rings
16.1 Rings . . . . . . . . . . . . . . . .
16.2 Integral Domains and Fields . . . .
16.3 Ring Homomorphisms and Ideals .
16.4 Maximal and Prime Ideals . . . . .
16.5 An Application to Software Design
16.6 Exercises . . . . . . . . . . . . . .
16.7 Programming Exercise . . . . . . .
16.8 References and Suggested Readings
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
227
227
231
233
237
240
244
249
249
.
.
.
.
251
251
255
259
265
17 Polynomials
17.1 Polynomial Rings . . . . . . . . . . . . . . . . . . .
17.2 The Division Algorithm . . . . . . . . . . . . . . .
17.3 Irreducible Polynomials . . . . . . . . . . . . . . .
17.4 Exercises . . . . . . . . . . . . . . . . . . . . . . .
17.5 Additional Exercises: Solving the Cubic and Quartic
Equations . . . . . . . . . . . . . . . . . . . . . . .
18 Integral Domains
18.1 Fields of Fractions . . . . . . . . .
18.2 Factorization in Integral Domains .
18.3 Exercises . . . . . . . . . . . . . .
18.4 References and Suggested Readings
19 Lattices and Boolean Algebras
19.1 Lattices . . . . . . . . . . . . . . .
19.2 Boolean Algebras . . . . . . . . . .
19.3 The Algebra of Electrical Circuits .
19.4 Exercises . . . . . . . . . . . . . .
19.5 Programming Exercises . . . . . .
19.6 References and Suggested Readings
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 268
271
271
275
284
287
.
.
.
.
.
.
.
.
.
.
.
.
.
.
288
. 288
. 292
. 298
. 301
. 303
. 304
xii
CONTENTS
20 Vector Spaces
20.1 Definitions and Examples . . . . .
20.2 Subspaces . . . . . . . . . . . . . .
20.3 Linear Independence . . . . . . . .
20.4 Exercises . . . . . . . . . . . . . .
20.5 References and Suggested Readings
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
305
305
307
308
310
313
21 Fields
21.1 Extension Fields . . . . . . . . . .
21.2 Splitting Fields . . . . . . . . . . .
21.3 Geometric Constructions . . . . . .
21.4 Exercises . . . . . . . . . . . . . .
21.5 References and Suggested Readings
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
315
315
326
328
334
337
22 Finite Fields
338
22.1 Structure of a Finite Field . . . . . . . . . . . . . . . 338
22.2 Polynomial Codes . . . . . . . . . . . . . . . . . . . 342
22.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . 351
22.4 Additional Exercises: Error Correction for BCH Codes353
22.5 References and Suggested Readings . . . . . . . . . . 354
23 Galois Theory
23.1 Field Automorphisms . . . . . . .
23.2 The Fundamental Theorem . . . .
23.3 Applications . . . . . . . . . . . . .
23.4 Exercises . . . . . . . . . . . . . .
23.5 References and Suggested Readings
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
356
356
361
369
375
377
379
389
Notation
404
1
Preliminaries
1.1
Abstract mathematics is different from other sciences. In laboratory sciences such as chemistry and physics, scientists perform experiments to discover new principles and verify theories. Although
mathematics is often motivated by physical experimentation or by
computer simulations, it is made rigorous through the use of logical arguments. In studying abstract mathematics, we take what is
called an axiomatic approach; that is, we take a collection of objects S and assume some rules about their structure. These rules
are called axioms. Using the axioms for S, we wish to derive other
information about S by using logical arguments. We require that
our axioms be consistent; that is, they should not contradict one
another. We also demand that there not be too many axioms. If
a system of axioms is too restrictive, there will be few examples of
the mathematical structure.
A statement in logic or mathematics is an assertion that is
either true or false. Consider the following examples:
3 + 56 13 + 8/2.
All cats are black.
2 + 3 = 5.
2x = 6 exactly when x = 4.
If ax2 + bx + c = 0 and a = 0, then
b b2 4ac
x=
.
2a
1
CHAPTER 1. PRELIMINARIES
x3 4x2 + 5x 6.
All but the first and last examples are statements, and must be
either true or false.
A mathematical proof is nothing more than a convincing
argument about the accuracy of a statement. Such an argument
should contain enough detail to convince the audience; for instance,
we can see that the statement 2x = 6 exactly when x = 4 is false
by evaluating 2 4 and noting that 6 = 8, an argument that would
satisfy anyone. Of course, audiences may vary widely: proofs can
be addressed to another student, to a professor, or to the reader of
a text. If more detail than needed is presented in the proof, then
the explanation will be either long-winded or poorly written. If
too much detail is omitted, then the proof may not be convincing.
Again it is important to keep the audience in mind. High school
students require much more detail than do graduate students. A
good rule of thumb for an argument in an introductory abstract
algebra course is that it should be written to convince ones peers,
whether those peers be other students or other readers of the text.
Let us examine different types of statements. A statement could
be as simple as 10/5 = 2; however, mathematicians are usually
interested in more complex statements such as If p, then q, where
p and q are both statements. If certain statements are known or
assumed to be true, we wish to know what we can say about other
statements. Here p is called the hypothesis and q is known as the
conclusion. Consider the following statement: If ax2 + bx + c = 0
and a = 0, then
x=
b2 4ac
.
2a
x=
b2 4ac
.
2a
Notice that the statement says nothing about whether or not the
hypothesis is true. However, if this entire statement is true and
we can show that ax2 + bx + c = 0 with a = 0 is true, then the
conclusion must be true. A proof of this statement might simply
be a series of equations:
ax2 + bx + c = 0
b
c
x2 + x =
a
a
( )2 ( )2
b
b
c
b
=
x2 + x +
a
2a
2a
a
(
)2
2
b
b 4ac
x+
=
2a
4a2
b
b2 4ac
x+
=
2a
2a
b b2 4ac
x=
.
2a
If we can prove a statement true, then that statement is called
a proposition. A proposition of major importance is called a
theorem. Sometimes instead of proving a theorem or proposition
all at once, we break the proof down into modules; that is, we
prove several supporting propositions, which are called lemmas,
and use the results of these propositions to prove the main result.
If we can prove a proposition or a theorem, we will often, with
very little effort, be able to derive other related propositions called
corollaries.
CHAPTER 1. PRELIMINARIES
Sometimes it is easier to prove the contrapositive of a statement. Proving the statement If p, then q is exactly the
same as proving the statement If not q, then not p.
Although it is usually better to find a direct proof of a theorem, this task can sometimes be difficult. It may be easier
to assume that the theorem that you are trying to prove is
false, and to hope that in the course of your argument you
are forced to make some statement that cannot possibly be
true.
Remember that one of the main objectives of higher mathematics is proving theorems. Theorems are tools that make new and
productive applications of mathematics possible. We use examples
to give insight into existing theorems and to foster intuitions as to
what new theorems might be true. Applications, examples, and
proofs are tightly interconnectedmuch more so than they may
seem at first appearance.
1.2
Set Theory
A set is a well-defined collection of objects; that is, it is defined
in such a manner that we can determine for any given object x
whether or not x belongs to the set. The objects that belong to a
set are called its elements or members. We will denote sets by
capital letters, such as A or X; if a is an element of the set A, we
write a A.
A set is usually specified either by listing all of its elements
inside a pair of braces or by stating the property that determines
whether or not an object x belongs to the set. We might write
X = {x1 , x2 , . . . , xn }
for a set containing elements x1 , x2 , . . . , xn or
X = {x : x satisfies P}
if each x in X satisfies a certain property P. For example, if E
is the set of even positive integers, we can describe E by writing
either
E = {2, 4, 6, . . .} or
Some of the more important sets that we will consider are the
following:
N = {n : n is a natural number} = {1, 2, 3, . . .};
Z = {n : n is an integer} = {. . . , 1, 0, 1, 2, . . .};
Q = {r : r is a rational number} = {p/q : p, q Z where q = 0};
R = {x : x is a real number};
C = {z : z is a complex number}.
We can find various relations between sets as well as perform
operations on sets. A set A is a subset of B, written A B or
B A, if every element of A is also an element of B. For example,
{4, 5, 8} {2, 3, 4, 5, 6, 7, 8, 9}
and
N Z Q R C.
Trivially, every set is a subset of itself. A set B is a proper subset
of a set A if B A but B = A. If A is not a subset of B, we write
A B; for example, {4, 7, 9} {2, 4, 5, 8, 9}. Two sets are equal,
written A = B, if we can show that A B and B A.
It is convenient to have a set with no elements in it. This set
is called the empty set and is denoted by . Note that the empty
set is a subset of every set.
To construct new sets out of old sets, we can perform certain
operations: the union A B of two sets A and B is defined as
A B = {x : x A or x B};
the intersection of A and B is defined by
A B = {x : x A and x B}.
If A = {1, 3, 5} and B = {1, 2, 3, 9}, then
A B = {1, 2, 3, 5, 9}
We can consider the union and the intersection of more than two
sets. In this case we write
n
Ai = A1 . . . An
i=1
and
Ai = A1 . . . An
i=1
CHAPTER 1. PRELIMINARIES
B = {x R : 2 x < 4}.
Then
A B = {x R : 2 x 3}
A B = {x R : 0 < x < 4}
A \ B = {x R : 0 < x < 2}
A = {x R : x 0 or x > 3}.
Proposition 1.2. Let A, B, and C be sets. Then
1. A A = A, A A = A, and A \ A = ;
2. A = A and A = ;
3. A (B C) = (A B) C and A (B C) = (A B) C;
4. A B = B A and A B = B A;
5. A (B C) = (A B) (A C);
6. A (B C) = (A B) (A C).
Proof. We will prove (1) and (3) and leave the remaining results
to be proven in the exercises.
(1) Observe that
A A = {x : x A or x A}
= {x : x A}
=A
and
A A = {x : x A and x A}
= {x : x A}
= A.
Also, A \ A = A A = .
(3) For sets A, B, and C,
A (B C) = A {x : x B or x C}
= {x : x A or x B, or x C}
= {x : x A or x B} C
= (A B) C.
A similar argument proves that A (B C) = (A B) C.
Theorem 1.3 (De Morgans Laws). Let A and B be sets. Then
1. (A B) = A B ;
2. (A B) = A B .
Proof. (1) We must show that (A B) A B and (A B)
A B . Let x (A B) . Then x
/ A B. So x is neither in A
nor in B, by the definition of the union of sets. By the definition
of the complement, x A and x B . Therefore, x A B and
we have (A B) A B .
To show the reverse inclusion, suppose that x A B . Then
x A and x B , and so x
/ A and x
/ B. Thus x
/ A B and
so x (AB) . Hence, (AB) A B and so (AB) = A B .
The proof of (2) is left as an exercise.
Example 1.4. Other relations between sets often hold true. For
example,
(A \ B) (B \ A) = .
To see that this is true, observe that
(A \ B) (B \ A) = (A B ) (B A )
= A A B B
= .
CHAPTER 1. PRELIMINARIES
We define the Cartesian product of n sets to be
A1 An = {(a1 , . . . , an ) : ai Ai for i = 1, . . . , n}.
B
1
B
f
C
g
gf
10
CHAPTER 1. PRELIMINARIES
and
(g f )(x) = g(f (x)) = 2x2 + 5.
In general, order makes a difference; that is, in most cases f g =
g f.
Example 1.12. Sometimes it is the case that f g = g f . Let
(f g)(x) = f (g(x)) = f ( 3 x ) = ( 3 x )3 = x
and
(g f )(x) = g(f (x)) = g(x3 ) =
x3 = x.
11
(
)
3 1
.
5 2
12
CHAPTER 1. PRELIMINARIES
(
=
)
2 1
;
5 3
(
)
3 0
B=
,
0 0
(
)
1 2 3
=
3 1 2
13
14
CHAPTER 1. PRELIMINARIES
1 2
1 1
(
)
18 33
and B =
,
11 20
(
)
1 0
.
0 1
15
16
CHAPTER 1. PRELIMINARIES
and so r t is divisible by n.
If we consider the equivalence relation established by the integers modulo 3, then
[0] = {. . . , 3, 0, 3, 6, . . .},
[1] = {. . . , 2, 1, 4, 7, . . .},
[2] = {. . . , 1, 2, 5, 8, . . .}.
Notice that [0] [1] [2] = Z and also that the sets are disjoint.
The sets [0], [1], and [2] form a partition of the integers.
The integers modulo n are a very important example in the
study of abstract algebra and will become quite useful in our investigation of various algebraic structures such as groups and rings. In
our discussion of the integers modulo n we have actually assumed
a result known as the division algorithm, which will be stated and
proved in Chapter 2.
1.3
Exercises
1. Suppose that
A = {x : x N and x is even},
B = {x : x N and x is prime},
C = {x : x N and x is a multiple of 5}.
Describe each of the following sets.
(a) A B
(c) A B
(b) B C
(d) A (B C)
(c) A B C
(b) B A
(d) A D
1.3. EXERCISES
17
7. Prove A (B C) = (A B) (A C).
8. Prove A B if and only if A B = A.
9. Prove (A B) = A B .
10. Prove A B = (A B) (A \ B) (B \ A).
11. Prove (A B) C = (A C) (B C).
12. Prove (A B) \ B = .
13. Prove (A B) \ B = A \ B.
14. Prove A \ (B C) = (A \ B) (A \ C).
15. Prove A (B \ C) = (A B) \ (A C).
16. Prove (A \ B) (B \ A) = (A B) \ (A B).
17. Which of the following relations f : Q Q define a mapping?
In each case, supply a reason why f is or is not a mapping.
p+1
p2
3p
(b) f (p/q) =
3q
(a) f (p/q) =
(c) f (p/q) =
p+q
q2
(d) f (p/q) =
3p2 p
7q 2
q
18
CHAPTER 1. PRELIMINARIES
x+1
.
x1
(d) m n in Z if m n
(mod 6)
19
29. (Projective Real Line) Define a relation on R2 \{(0, 0)} by letting (x1 , y1 ) (x2 , y2 ) if there exists a nonzero real number such
that (x1 , y1 ) = (x2 , y2 ). Prove that defines an equivalence
relation on R2 \ (0, 0). What are the corresponding equivalence
classes? This equivalence relation defines the projective line, denoted by P(R), which is very important in geometry.
1.4
[1]
[2]
[3]
[4]
[5]
[6]
Gallian, J. A. Contemporary Abstract Algebra. 7th ed. Brooks/Cole, Belmont, CA, 2009.
[7]
[8]
[9]
[10] Lang, S. Algebra. 3rd ed. Springer, New York, 2002. Another
standard graduate text.
[11] Lidl, R. and Pilz, G. Applied Abstract Algebra.
Springer, New York, 1998.
2nd ed.
20
CHAPTER 1. PRELIMINARIES
2
The Integers
The integers are the building blocks of mathematics. In this chapter we will investigate the fundamental properties of the integers,
including mathematical induction, the division algorithm, and the
Fundamental Theorem of Arithmetic.
2.1
Mathematical Induction
n(n + 1)
2
for any natural number n. This formula is easily verified for small
numbers such as n = 1, 2, 3, or 4, but it is impossible to verify for
all natural numbers on a case-by-case basis. To prove the formula
true in general, a more generic method is required.
Suppose we have verified the equation for the first n cases. We
will attempt to show that we can generate the formula for the
(n + 1)th case from this knowledge. The formula is true for n = 1
since
1(1 + 1)
.
1=
2
If we have verified the first n cases, then
n(n + 1)
+n+1
2
n2 + 3n + 2
=
2
(n + 1)[(n + 1) + 1]
=
.
2
1 + 2 + + n + (n + 1) =
22
that if the statement holds for a given case, then it must also hold
for the next case in the sequence. We summarize mathematical
induction in the following axiom.
Principle 2.1 (First Principle of Mathematical Induction). Let
S(n) be a statement about integers for n N and suppose S(n0 ) is
true for some integer n0 . If for all integers k with k n0 , S(k)
implies that S(k + 1) is true, then S(n) is true for all integers n
greater than or equal to n0 .
Example 2.2. For all integers n 3, 2n > n + 4. Since
8 = 23 > 3 + 4 = 7,
the statement is true for n0 = 3. Assume that 2k > k + 4 for k 3.
Then 2k+1 = 2 2k > 2(k + 4). But
2(k + 4) = 2k + 8 > k + 5 = (k + 1) + 4
since k is positive. Hence, by induction, the statement holds for all
integers n 3.
Example 2.3. Every integer 10n+1 + 3 10n + 5 is divisible by 9
for n N. For n = 1,
101+1 + 3 10 + 5 = 135 = 9 15
is divisible by 9. Suppose that 10k+1 + 3 10k + 5 is divisible by 9
for k 1. Then
10(k+1)+1 + 3 10k+1 + 5 = 10k+2 + 3 10k+1 + 50 45
= 10(10k+1 + 3 10k + 5) 45
is divisible by 9.
Example 2.4. We will prove the binomial theorem using mathematical induction; that is,
n ( )
n k nk
a b
,
(a + b) =
k
n
k=0
23
n k n+1k
k+1 nk
=
a b
+
a b
k
k
k=0
k=0
)
n (
n ( )
n
n k n+1k
= an+1 +
ak bn+1k +
a b
+ bn+1
k1
k
k=1
k=1
) ( )]
n [(
n
n
= an+1 +
+
ak bn+1k + bn+1
k1
k
k=1
(
n+1
n + 1)
ak bn+1k .
=
k
k=0
We have an equivalent statement of the Principle of Mathematical Induction that is often very useful.
Principle 2.5 (Second Principle of Mathematical Induction). Let
S(n) be a statement about integers for n N and suppose S(n0 ) is
true for some integer n0 . If S(n0 ), S(n0 + 1), . . . , S(k) imply that
S(k + 1) for k n0 , then the statement S(n) is true for all integers
n n0 .
A nonempty subset S of Z is well-ordered if S contains a least
element. Notice that the set Z is not well-ordered since it does not
contain a smallest element. However, the natural numbers are wellordered.
Principle 2.6 (Principle of Well-Ordering). Every nonempty subset of the natural numbers is well-ordered.
The Principle of Well-Ordering is equivalent to the Principle of
Mathematical Induction.
Lemma 2.7. The Principle of Mathematical Induction implies that
1 is the least positive natural number.
24
2.2
25
and a = bq + r , 0 r < b.
26
27
Prime Numbers
Let p be an integer such that p > 1. We say that p is a prime
number, or simply p is prime, if the only positive numbers that
divide p are 1 and p itself. An integer n > 1 that is not prime is
said to be composite.
Lemma 2.13 (Euclid). Let a and b be integers and p be a prime
number. If p | ab, then either p | a or p | b.
Proof. Suppose that p does not divide a. We must show that
p | b. Since gcd(a, p) = 1, there exist integers r and s such that
ar + ps = 1. So
b = b(ar + ps) = (ab)r + p(bs).
Since p divides both ab and itself, p must divide b = (ab)r + p(bs).
28
2.3. EXERCISES
29
Historical Note
22 + 1 = 4,294,967,297
is a composite number. One of the many unproven conjectures
about prime numbers is Goldbachs Conjecture. In a letter to Euler
in 1742, Christian Goldbach stated the conjecture that every even
integer with the exception of 2 seemed to be the sum of two primes:
4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, . . .. Although the conjecture has
been verified for the numbers up through 4 1018 , it has yet to be
proven in general. Since prime numbers play an important role in
public key cryptography, there is currently a great deal of interest
in determining whether or not a large number is prime.
Sage Sages original purpose was to support research in number theory, so it is perfect for the types of computations with the
integers that we have in this chapter.
2.3 Exercises
1. Prove that
12 + 22 + + n2 =
n(n + 1)(2n + 1)
6
for n N.
2. Prove that
13 + 23 + + n3 =
n2 (n + 1)2
4
for n N.
3. Prove that n! > 2n for n 4.
4. Prove that
x + 4x + 7x + + (3n 2)x =
for n N.
n(3n 1)x
2
30
1
n
a1 a2 an
ak .
n
n
k=1
8. Prove the Leibniz rule for f (n) (x), where f (n) is the nth derivative of f ; that is, show that
(f g)(n) (x) =
n ( )
n
k=0
2.3. EXERCISES
31
(a) 14 and 39
32
2.4
Programming Exercises
33
2.5
[1]
[2]
Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, New York,
2008.
[3]
[4]
3
Groups
We begin our study of algebraic structures by investigating sets associated with single operations that satisfy certain reasonable axioms; that is, we want to define an operation on a set in a way that
will generalize such familiar structures as the integers Z together
with the single operation of addition, or invertible 2 2 matrices
together with the single operation of matrix multiplication. The
integers and the 22 matrices, together with their respective single
operations, are examples of algebraic structures known as groups.
The theory of groups occupies a central position in mathematics. Modern group theory arose from an attempt to find the roots
of a polynomial in terms of its coefficients. Groups now play a central role in such areas as coding theory, counting, and the study
of symmetries; many areas of biology, chemistry, and physics have
benefited from group theory.
3.1
7 3 1 (mod 5)
3 + 5 0 (mod 8)
3 5 7 (mod 8)
3 + 4 7 (mod 12)
3 4 0 (mod 12)
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
7
2
0
2
4
6
0
2
4
6
3
0
3
6
1
4
7
2
5
4
0
4
0
4
0
4
0
4
5
0
5
2
7
4
1
6
3
6
0
6
4
2
0
6
4
2
7
0
7
6
5
4
3
2
1
36
CHAPTER 3. GROUPS
1. Addition and multiplication are commutative:
a+bb+a
(mod n)
ab ba (mod n).
2. Addition and multiplication are associative:
(a + b) + c a + (b + c)
(mod n)
(mod n).
(mod n).
Proof. We will prove (1) and (6) and leave the remaining properties to be proven in the exercises.
(1) Addition and multiplication are commutative modulo n
since the remainder of a + b divided by n is the same as the remainder of b + a divided by n.
(6) Suppose that gcd(a, n) = 1. Then there exist integers r and
s such that ar + ns = 1. Since ns = 1 ar, it must be the case that
ar 1 (mod n). Letting b be the equivalence class of r, ab 1
(mod n).
Conversely, suppose that there exists an integer b such that
ab 1 (mod n). Then n divides ab 1, so there is an integer k
such that ab nk = 1. Let d = gcd(a, n). Since d divides ab nk,
d must also divide 1; hence, d = 1.
Symmetries
horizontal axis
C
A
identity
180
rotation
reflection
vertical axis
reflection
38
CHAPTER 3. GROUPS
B
)
(
A B C
id =
A B C
identity
A
C
A
rotation
A
1 =
(
2 =
B
B
2 =
A B C
C B A
reflection
A
)
(
A B C
1 =
A C B
reflection
A
A B C
C A B
reflection
A
rotation
A
A B C
B C A
3 =
A B C
B A C
39
1
1
3
2
id
2
1
2
2
1
3
1
id
2
3
3
2
1
2
1
id
3.2
40
CHAPTER 3. GROUPS
There exists an element e G, called the identity element,
such that for any element a G
e a = a e = a.
For each element a G, there exists an inverse element in
G, denoted by a1 , such that
a a1 = a1 a = e.
+
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
4
4
0
1
2
3
41
12=2
22=4
32=0
42=2
5 2 = 4.
1
3
5
7
1
1
3
5
7
3
3
1
7
5
5
5
7
1
3
7
7
5
3
1
42
CHAPTER 3. GROUPS
1
ad bc
)
d b
.
c a
0
1
i
0
0
I=
1
(
i
K=
0
1
0
)
0
,
i
a bi
a2 + b2
43
44
CHAPTER 3. GROUPS
and
g n = g 1 g 1 g 1 .
|
{z
}
n times
3.3. SUBGROUPS
45
3.3
Subgroups
46
CHAPTER 3. GROUPS
(
=
)
d b
.
c a
+
(0, 0)
(0, 1)
(1, 0)
(1, 1)
(0, 0)
(0, 0)
(0, 1)
(1, 0)
(1, 1)
(0, 1)
(0, 1)
(0, 0)
(1, 1)
(1, 0)
(1, 0)
(1, 0)
(1, 1)
(0, 0)
(0, 1)
(1, 1)
(1, 1)
(1, 0)
(0, 1)
(0, 0)
3.3. SUBGROUPS
47
48
3.4
CHAPTER 3. GROUPS
Exercises
(d) 9x 3 (mod 5)
(e) 5x 1 (mod 6)
(f) 3x 1 (mod 6)
(c)
a
b
c
d
a
a
b
c
d
b
c
b
d
a
c
d
c
a
b
d
a
d
b
c
(b)
a
b
c
d
a
a
b
c
d
b
b
c
d
a
c
c
d
a
b
d
d
a
b
c
a
b
c
d
a
a
b
c
d
b
b
a
b
d
c
c
c
a
b
d
d
d
d
c
(d)
a
b
c
d
a
a
b
c
d
b
b
a
d
c
c
c
d
a
b
d
d
c
b
a
3.4. EXERCISES
49
1 x
0 1
0 0
of the form
y
z
1
1 x y
1 x y
1 x + x y + y + xz
0 1 z 0 1 z = 0
1
z + z .
0 0 1
0
0
1
0 0 1
11. Prove that det(AB) = det(A) det(B) in GL2 (R). Use this
result to show that the binary operation in the group GL2 (R) is
closed; that is, if A and B are in GL2 (R), then AB GL2 (R).
12. Let Zn2 = {(a1 , a2 , . . . , an ) : ai Z2 }. Define a binary operation on Zn2 by
(a1 , a2 , . . . , an ) + (b1 , b2 , . . . , bn ) = (a1 + b1 , a2 + b2 , . . . , an + bn ).
Prove that Zn2 is a group under this operation. This group is important in algebraic coding theory.
13. Show that R = R \ {0} is a group under the operation of
multiplication.
14. Given the groups R and Z, let G = R Z. Define a binary
operation on G by (a, m) (b, n) = (ab, m + n). Show that G is
a group under this operation.
15. Prove or disprove that every group containing six elements is
abelian.
16. Give a specific example of some group G and elements g, h G
where (gh)n = g n hn .
17. Give an example of three different groups with eight elements.
Why are the groups different?
18. Show that there are n! permutations of a set containing n
items.
50
CHAPTER 3. GROUPS
(mod n)
for all a Zn .
20. Prove that there is a multiplicative identity for the integers
modulo n:
a 1 a (mod n).
21. For each a Zn find an element b Zn such that
a+bb+a0
(mod n).
22. Show that addition and multiplication mod n are well defined
operations. That is, show that the operations do not depend on
the choice of the representative from the equivalence classes mod
n.
23. Show that addition and multiplication mod n are associative
operations.
24. Show that multiplication distributes over addition modulo n:
a(b + c) ab + ac (mod n).
25. Let a and b be elements in a group G. Prove that abn a1 =
(aba1 )n for n Z.
26. Let U (n) be the group of units in Zn . If n > 2, prove that
there is an element k U (n) such that k 2 = 1 and k = 1.
1
27. Prove that the inverse of g1 g2 gn is gn1 gn1
g11 .
3.4. EXERCISES
51
33. Let G be a group and suppose that (ab)2 = a2 b2 for all a and
b in G. Prove that G is an abelian group.
34. Find all the subgroups of Z3 Z3 . Use this information to
show that Z3 Z3 is not the same group as Z9 . (See Example 3.28
for a short description of the product of groups.)
35. Find all the subgroups of the symmetry group of an equilateral
triangle.
36. Compute the subgroups of the symmetry group of a square.
37. Let H = {2k : k Z}. Show that H is a subgroup of Q .
38. Let n = 0, 1, 2, . . . and nZ = {nk : k Z}. Prove that nZ is a
subgroup of Z. Show that these subgroups are the only subgroups
of Z.
39. Let T = {z C : |z| = 1}. Prove that T is a subgroup of C .
40.
(
)
cos sin
sin cos
52
CHAPTER 3. GROUPS
3.5
53
(c) Write a formula to calculate the check digit, d12 , in the UPC
number.
(d) The UPC error detection scheme can detect most transposition errors; that is, it can determine if two digits have been interchanged. Show that the transposition error 0-05000-300426 is not detected. Find a transposition error that is detected.
Can you find a general rule for the types of transposition errors that can be detected?
(e) Write a program that will determine whether or not a UPC
number is valid.
(mod n)
to mean
d1 w1 + d2 w2 + + dk wk 0 (mod n).
Suppose that (d1 , d2 , . . . , dk )(w1 , w2 , . . . , wk ) 0 (mod n) is an error detection scheme for the k-digit identification number d1 d2 dk ,
where 0 di < n. Prove that all single-digit errors are detected if
and only if gcd(wi , n) = 1 for 1 i k.
3. Let (d1 , d2 , . . . , dk ) (w1 , w2 , . . . , wk ) 0 (mod n) be an error
detection scheme for the k-digit identification number d1 d2 dk ,
where 0 di < n. Prove that all transposition errors of two digits
di and dj are detected if and only if gcd(wi wj , n) = 1 for i and
j between 1 and k.
4. ISBN CodesEvery book has an International Standard Book
Number (ISBN) code. This is a 10-digit code indicating the books
publisher and title. The tenth digit is a check digit satisfying
(d1 , d2 , . . . , d10 ) (10, 9, . . . , 1) 0
(mod 11).
54
CHAPTER 3. GROUPS
3.6
[1]
[2]
[3]
Gallian, J. A. Contemporary Abstract Algebra. 7th ed. Brooks/Cole, Belmont, CA, 2009.
[4]
[5]
[6]
4
Cyclic Groups
The groups Z and Zn , which are among the most familiar and
easily understood groups, are both examples of what are called
cyclic groups. In this chapter we will study the properties of cyclic
groups and cyclic subgroups, which play a fundamental part in the
classification of all abelian groups.
4.1
Cyclic Subgroups
56
22 = 4
23 = 8
24 = 7
25 = 5
26 = 1.
57
S3
{id, 1 , 2 }
{id, 1 }
{id, 2 }
{id, 3 }
{id}
Figure 4.8: Subgroups of S3
Theorem 4.9. Every cyclic group is abelian.
Proof. Let G be a cyclic group and a G be a generator for G.
If g and h are in G, then they can be written as powers of a, say
g = ar and h = as . Since
gh = ar as = ar+s = as+r = as ar = hg,
G is abelian.
58
and H is generated by h.
Corollary 4.11. The subgroups of Z are exactly nZ for n =
0, 1, 2, . . ..
Proposition 4.12. Let G be a cyclic group of order n and suppose
that a is a generator for G. Then ak = e if and only if n divides k.
29=2
3 9 = 11
49=4
5 9 = 13
69=6
7 9 = 15
89=8
99=1
10 9 = 10
11 9 = 3
12 9 = 12
13 9 = 5
14 9 = 14
15 9 = 7.
4.2
a bi
.
a2 + b2
|z| = 13
z 1 =
z = 2 3i.
60
0
z2 = 1 2i
a2 + b2
and
a = r cos
b = r sin .
b = 2 sin 60 =
3.
representation. If z = 3 2 3 2 i, then
r = a2 + b2 = 36 = 6
( )
b
= arctan
= arctan(1) = 315 ,
a
and
so 3 2 3 2 i = 6 cis 315 .
62
63
2
2
=
+
i
2
2
2
2
3 =
+
i
2
2
2
2
5 =
i
2 2
2
2
i.
7 =
2
2
y
i
3
1
0
5
7
i
4.3
Computing large powers can be very time-consuming. Just as anyone can compute 22 or 28 , everyone knows how to compute
22
1000000
64
a2
a
(mod n)
21
a2
(mod n)
..
.
(mod n).
0 +26 +28
(mod 481).
(mod 481).
2
We can square this result to obtain a value for 2712 (mod 481):
2
2712 (2712 )2
(329)
108,241
16
(mod 481)
(mod 481)
(mod 481)
(mod 481).
n
2712 419
(mod 481)
and
8
n+1
4.4. EXERCISES
65
Therefore,
0 +26 +28
271321 2712
20
271
26
271
(mod 481)
8
2712
(mod 481)
4.4 Exercises
1. Prove or disprove each of the following statements.
(a) All of the generators of Z60 are prime.
(b) U (8) is cyclic.
(c) Q is cyclic.
(d) If every proper subgroup of a group G is cyclic, then G is a
cyclic group.
(e) A group with a finite number of subgroups is finite.
2. Find the order of each of the following elements.
(a) 5 Z12
(b) 3 R
(c) 3 R
(d) i C
(e) 72 in Z240
(f) 312 in Z471
66
(g)
(h)
(i)
(j)
(k)
(l)
(m)
subgroup
subgroup
subgroup
subgroup
subgroup
subgroup
subgroup
generated by 3 in U (20)
generated by 5 in U (18)
of R generated by 7
of C generated by i where i2 = 1
of C generated by 2i
of C generated by (1 + i)/ 2
of C generated by (1 + 3 i)/2
4. Find the subgroups of GL2 (R) generated by each of the following matrices.
(
)
(
)
(
)
0 1
1 1
1 1
(a)
(c)
(e)
1 0
1 0
1 0
(
)
(
)
(
)
0 1/3
1 1
3/2 1/2
(b)
(d)
(f)
3 0
0 1
1/2
3/2
5. Find the order of every element in Z18 .
6. Find the order of every element in the symmetry group of the
square, D4 .
7. What are all of the cyclic subgroups of the quaternion group,
Q8 ?
8. List all of the cyclic subgroups of U (30).
9. List every generator of each subgroup of order 8 in Z32 .
10. Find all elements of finite order in each of the following groups.
Here the indicates the set with zero removed.
(b) Q
(a) Z
(c) R
(
A=
)
0 1
1 0
and
(
)
0 1
B
1 1
be elements in GL2 (R). Show that A and B have finite orders but
AB does not.
4.4. EXERCISES
67
(d) (9 i)(9 i)
(e) i45
(f) (1 + i) + (1 + i)
(c) 3 cis()
(b) 5 cis(9/4)
(d) cis(7/4)/2
(e) 3i
(c) 2 + 2i
(d) 3 + i
(b) 5
(f) 2i + 2 3
(1 + i)1
(1 i)6
( 3 + i)5
(i)10
(f) ( 2 2 i)12
(g) (2 + 2i)5
(b) zz = |z|2
(c)
z 1
z/|z|2
20. List and graph the 6th roots of unity. What are the generators
of this group? What are the primitive 6th roots of unity?
21. List and graph the 5th roots of unity. What are the generators
of this group? What are the primitive 5th roots of unity?
22. Calculate each of the following.
(a) 2923171 (mod 582)
68
69
4.5
Programming Exercises
4.6
[1]
[2]
70
5
Permutation Groups
Permutation groups are central to the study of geometric symmetries and to Galois theory, the study of finding solutions of
polynomial equations. They also provide abundant examples of
nonabelian groups.
Let us recall for a moment the symmetries of the equilateral
triangle ABC from Chapter 3. The symmetries actually consist
of permutations of the three vertices, where a permutation of the
set S = {A, B, C} is a one-to-one and onto map : S S. The
three vertices have the following six permutations.
(
)
(
)
(
)
A B C
A B C
A B C
A B C
C A B
B C A
(
)
(
)
(
)
A B C
A B C
A B C
A C B
C B A
B A C
We have used the array
(
A B C
B C A
5.1
72
2 3 4 5
2 3 5 4
2 3 4 5
2 1 4 5
)
)
)
2 3 4 5
.
2 1 5 4
The following table tells us how to multiply elements in the permutation group G.
id
id id
id
id
id
73
(
)
1 2 3 4
=
,
1 4 3 2
but
(
)
1 2 3 4
=
.
3 2 1 4
Cycle Notation
The notation that we have used to represent permutations up to
this point is cumbersome, to say the least. To work effectively
with permutation groups, we need a more streamlined method of
writing down and manipulating permutations.
A permutation SX is a cycle of length k if there exist
elements a1 , a2 , . . . , ak X such that
(a1 ) = a2
(a2 ) = a3
..
.
(ak ) = a1
and (x) = x for all other elements x X. We will write (a1 , a2 , . . . , ak )
to denote the cycle . Cycles are the building blocks of all permutations.
Example 5.5. The permutation
(
)
1 2 3 4 5 6 7
=
= (162354)
6 3 5 1 4 2 7
is a cycle of length 6, whereas
(
)
1 2 3 4 5 6
=
= (243)
1 4 2 3 5 6
is a cycle of length 3.
Not every permutation is a cycle. Consider the permutation
(
)
1 2 3 4 5 6
= (1243)(56).
2 4 1 3 6 5
This permutation actually contains a cycle of length 2 and a cycle
of length 4.
74
3 7 5,
5 7 2,
2 7 1,
and as
2 7 5,
5 7 6,
6 7 2,
3 7 5,
5 7 6,
6 7 2 7 1,
75
(x) x Xi
x
x
/ Xi ,
2 3 4 5 6
4 3 1 5 2
)
2 3 4 5 6
.
2 1 5 6 4
76
Transpositions
The simplest permutation is a cycle of length 2. Such cycles are
called transpositions. Since
(a1 , a2 , . . . , an ) = (a1 an )(a1 an1 ) (a1 a3 )(a1 a2 ),
any cycle can be written as the product of transpositions, leading
to the following proposition.
Proposition 5.12. Any permutation of a finite set containing at
least two elements can be written as the product of transpositions.
Example 5.13. Consider the permutation
(16)(253) = (16)(23)(25) = (16)(45)(23)(45)(25).
As we can see, there is no unique way to represent permutation
as the product of transpositions. For instance, we can write the
identity permutation as (12)(12), as (13)(24)(13)(24), and in many
other ways. However, as it turns out, no permutation can be written as the product of both an even number of transpositions and
an odd number of transpositions. For instance, we could represent
the permutation (16) by
(23)(16)(23)
or by
(35)(16)(13)(16)(13)(35)(56),
but (16) will always be the product of an odd number of transpositions.
Lemma 5.14. If the identity is written as the product of r transpositions,
id = 1 2 r ,
then r is an even number.
Proof. We will employ induction on r. A transposition cannot
be the identity; hence, r > 1. If r = 2, then we are done. Suppose
that r > 2. In this case the product of the last two transpositions,
r1 r , must be one of the following cases:
(ab)(ab) = id
(bc)(ab) = (ac)(bc)
(cd)(ab) = (ab)(cd)
(ac)(ab) = (ab)(bc),
where a, b, c, and d are distinct.
77
78
(12)(34)
(13)(24)
(14)(23)
(123)
(132)
(124)
(142)
(134)
(143)
(234)
(243).
79
Historical Note
Lagrange first thought of permutations as functions from a set
to itself, but it was Cauchy who developed the basic theorems and
notation for permutations. He was the first to use cycle notation.
Augustin-Louis Cauchy (17891857) was born in Paris at the height
of the French Revolution. His family soon left Paris for the village
of Arcueil to escape the Reign of Terror. One of the familys neighbors there was Pierre-Simon Laplace (17491827), who encouraged
him to seek a career in mathematics. Cauchy began his career as
a mathematician by solving a problem in geometry given to him
by Lagrange. Cauchy wrote over 800 papers on such diverse topics
as differential equations, finite groups, applied mathematics, and
complex analysis. He was one of the mathematicians responsible
for making calculus rigorous. Perhaps more theorems and concepts
in mathematics have the name Cauchy attached to them than that
of any other mathematician.
5.2
Dihedral Groups
n1
3
4
80
2
3
7
6
1
rotation
4
5
4
5
1
6
1
2
3
7
6
2
reflection
7
6
2
4
Proof. The possible motions of a regular n-gon are either reflections or rotations (Figure 5.21). There are exactly n possible
rotations:
360
360
360
id,
,2
, . . . , (n 1)
.
n
n
n
81
360
.
n
82
2
3
3
2
4
1
5.3. EXERCISES
83
3
2
1
3
4
1
5.3
Exercises
(
)
1 2 3 4 5
2 4 1 5 3
(c)
(
)
1 2 3 4 5
3 5 1 4 2
(b)
)
(
1 2 3 4 5
4 2 5 1 3
(d)
)
(
1 2 3 4 5
1 4 3 2 5
(i) (123)(45)(1254)2
(b) (12)(1253)
(j) (1254)100
(c) (143)(23)(24)
(k) |(1254)|
(d) (1423)(34)(56)(1324)
(l) |(1254)2 |
(e) (1254)(13)(25)
(m) (12)1
(f) (1254)(13)(25)2
(n) (12537)1
(o) [(12)(34)(12)(47)]1
(p) [(1235)(467)]1
3. Express the following permutations as products of transpositions and identify them as even or odd.
84
(a) (14356)
(b) (156)(234)
(c) (1426)(142)
(d) (17254)(1423)(154632)
(e) (142637)
4. Find (a1 , a2 , . . . , an )1 .
5. List all of the subgroups of S4 . Find each of the following sets.
(a) { S4 : (1) = 3}
(b) { S4 : (2) = 2}
(c) { S4 : (1) = 3 and (2) = 2}
Are any of these sets subgroups of S4 ?
6. Find all of the subgroups in A4 . What is the order of each
subgroup?
7. Find all possible orders of elements in S7 and A7 .
8. Show that A10 contains an element of order 15.
9. Does A8 contain an element of order 26?
10. Find an element of largest order in Sn for n = 3, . . . , 10.
11. What are the possible cycle structures of elements of A5 ?
What about A6 ?
12. Let Sn have order n. Show that for all integers i and j,
i = j if and only if i j (mod n).
13. Let = 1 m Sn be the product of disjoint cycles. Prove
that the order of is the least common multiple of the lengths of
the cycles 1 , . . . , m .
14. Using cycle notation, list the elements in D5 . What are r and
s? Write every element as a product of r and s.
15. If the diagonals of a cube are labeled as Figure 5.26, to which
motion of the cube does the permutation (12)(34) correspond?
What about the other permutations of the diagonals?
16. Find the group of rigid motions of a tetrahedron. Show that
this is the same group as A4 .
17. Prove that Sn is nonabelian for n 3.
18. Show that An is nonabelian for n 4.
19. Prove that Dn is nonabelian for n 3.
5.3. EXERCISES
85
86
6
Cosets and Lagranges
Theorem
6.1
Cosets
88
Example 6.2. Let H be the subgroup of S3 defined by the permutations {(1), (123), (132)}. The left cosets of H are
(1)H = (123)H = (132)H = {(1), (123), (132)}
(12)H = (13)H = (23)H = {(12), (13), (23)}.
The right cosets of H are exactly the same as the left cosets:
H(1) = H(123) = H(132) = {(1), (123), (132)}
H(12) = H(13) = H(23) = {(12), (13), (23)}.
It is not always the case that a left coset is the same as a right
coset. Let K be the subgroup of S3 defined by the permutations
{(1), (12)}. Then the left cosets of K are
(1)K = (12)K = {(1), (12)}
(13)K = (123)K = {(13), (123)}
(23)K = (132)K = {(23), (132)};
however, the right cosets of K are
K(1) = K(12) = {(1), (12)}
K(13) = K(132) = {(13), (132)}
K(23) = K(123) = {(23), (123)}.
The following lemma is quite useful when dealing with cosets.
(We leave its proof as an exercise.)
Lemma 6.3. Let H be a subgroup of a group G and suppose that
g1 , g2 G. The following conditions are equivalent.
1. g1 H = g2 H;
2. Hg11 = Hg21 ;
3. g1 H g2 H;
4. g2 g1 H;
5. g11 g2 H.
In all of our examples the cosets of a subgroup H partition the
larger group G. The following theorem proclaims that this will
always be the case.
Theorem 6.4. Let H be a subgroup of a group G. Then the left
cosets of H in G partition G. That is, the group G is the disjoint
union of the left cosets of H in G.
Proof. Let g1 H and g2 H be two cosets of H in G. We must
show that either g1 H g2 H = or g1 H = g2 H. Suppose that
g1 H g2 H = and a g1 H g2 H. Then by the definition of a left
coset, a = g1 h1 = g2 h2 for some elements h1 and h2 in H. Hence,
g1 = g2 h2 h1
1 or g1 g2 H. By Lemma 6.3, g1 H = g2 H.
89
6.2
Lagranges Theorem
90
|G|
|G| |H|
=
= [G : H][H : K].
|K|
|H| |K|
91
6.3
92
(mod p).
6.4. EXERCISES
6.4
93
Exercises
8 in Z24
3 in U (8)
3Z in Z
A4 in S4
An in Sn
(f) D4 in S4
(g) T in C
(h) H = {(1), (123), (132)} in
S4
6. Describe the left cosets of SL2 (R) in GL2 (R). What is the index
of SL2 (R) in GL2 (R)?
7. Verify Eulers Theorem for n = 15 and a = 4.
8. Use Fermats Little Theorem to show that if p = 4n+3 is prime,
there is no solution to the equation x2 1 (mod p).
9. Show that the integers have infinite index in the additive group
of rational numbers.
10. Show that the additive group of real numbers has infinite index
in the additive group of the complex numbers.
11. Let H be a subgroup of a group G and suppose that g1 , g2 G.
Prove that the following conditions are equivalent.
(a) g1 H = g2 H
(b) Hg11 = Hg21
(c) g1 H g2 H
(d) g2 g1 H
(e) g11 g2 H
94
d|n
(d)
7
Introduction to
Cryptography
96
7.1
97
98
)
2 21
.
25 3
If b = (2, 2)t , then our message is encrypted as RRCR. The encrypted letter R represents more than one plaintext letter.
Frequency analysis can still be performed on a polyalphabetic
cryptosystem, because we have a good understanding of how pairs
of letters appear in the English language. The pair th appears
quite often; the pair qz never appears. To avoid decryption by a
third party, we must use a larger matrix than the one we used in
Example 7.4.
99
100
Message Verification
There is a problem of message verification in public key cryptosystems. Since the encoding key is public knowledge, anyone has the
ability to send an encoded message. If Alice receives a message
from Bob, she would like to be able to verify that it was Bob
who actually sent the message. Suppose that Bobs encrypting key
is (n , E ) and his decrypting key is (n , D ). Also, suppose that
Alices encrypting key is (n, E) and her decrypting key is (n, D).
Since encryption keys are public information, they can exchange
coded messages at their convenience. Bob wishes to assure Alice
that the message he is sending is authentic. Before Bob sends the
message x to Alice, he decrypts x with his own key:
x = xD mod n .
101
a message that only Alice can decode. Alice decodes the message
and then encodes the result with Bobs key to read the original
message, a message that could have only been sent by Bob.
Historical Note
Encrypting secret messages goes as far back as ancient Greece
and Rome. As we know, Julius Caesar used a simple shift code
to send and receive messages. However, the formal study of encoding and decoding messages probably began with the Arabs in
the 1400s. In the fifteenth and sixteenth centuries mathematicians
such as Alberti and Viete discovered that monoalphabetic cryptosystems offered no real security. In the 1800s, F. W. Kasiski
established methods for breaking ciphers in which a ciphertext letter can represent more than one plaintext letter, if the same key
was used several times. This discovery led to the use of cryptosystems with keys that were used only a single time. Cryptography
was placed on firm mathematical foundations by such people as W.
Friedman and L. Hill in the early part of the twentieth century.
The period after World War I saw the development of specialpurpose machines for encrypting and decrypting messages, and
mathematicians were very active in cryptography during World
War II. Efforts to penetrate the cryptosystems of the Axis nations
were organized in England and in the United States by such notable mathematicians as Alan Turing and A. A. Albert. The Allies
gained a tremendous advantage in World War II by breaking the ciphers produced by the German Enigma machine and the Japanese
Purple ciphers.
By the 1970s, interest in commercial cryptography had begun
to take hold. There was a growing need to protect banking transactions, computer data, and electronic mail. In the early 1970s,
IBM developed and implemented LUZIFER, the forerunner of the
National Bureau of Standards Data Encryption Standard (DES).
The concept of a public key cryptosystem, due to Diffie and
Hellman, is very recent (1976). It was further developed by Rivest,
Shamir, and Adleman with the RSA cryptosystem (1978). It is not
known how secure any of these systems are. The trapdoor knapsack
cryptosystem, developed by Merkle and Hellman, has been broken.
It is still an open question whether or not the RSA system can be
broken. In 1991, RSA Laboratories published a list of semiprimes
(numbers with exactly two prime factors) with a cash prize for whoever was able to provide a factorization (http://www.emc.com/emcplus/rsa-labs/historical/the-rsa-challenge-numbers.htm). Although
102
the challenge ended in 2007, many of these numbers have not yet
been factored.
There been a great deal of controversy about research in cryptography and cryptography itself. In 1929, when Henry Stimson, Secretary of State under Herbert Hoover, dismissed the Black
Chamber (the State Departments cryptography division) on the
ethical grounds that gentlemen do not read each others mail.
During the last two decades of the twentieth century, the National
Security Agency wanted to keep information about cryptography
secret, whereas the academic community fought for the right to
publish basic research. Currently, research in mathematical cryptography and computational number theory is very active, and
mathematicians are free to publish their results in these areas.
Sage Sages early development featured powerful routines for
number theory, and later included significant support for algebraic structures and other areas of discrete mathematics. So it
is a natural tool for the study of cryptology, including topics like
RSA, elliptic curve cryptography, and AES (Advanced Encryption
Standard).
7.3
Exercises
7.3. EXERCISES
103
(
)
3 4
A=
,
2 3
use the encryption function f (p) = Ap + b to encode the message CRYPTOLOGY, where b = (2, 5)t . What is the decoding
function?
7. Encrypt each of the following RSA messages x so that x is
divided into blocks of integers of length 2; that is, if x = 142528,
encode 14, 25, and 28 separately.
(a) n = 3551, E = 629, x = 31
(b) n = 2257, E = 47, x = 23
(c) n = 120979, E = 13251, x = 142371
(d) n = 45629, E = 781, x = 231561
8. Compute the decoding key D for each of the encoding keys in
Exercise 7.
9. Decrypt each of the following RSA messages y.
(a) n = 3551, D = 1997, y = 2791
(b) n = 5893, D = 81, y = 34
(c) n = 120979, D = 27331, y = 112135
(d) n = 79403, D = 671, y = 129381
10. For each of the following encryption keys (n, E) in the RSA
cryptosystem, compute D.
(a) (n, E) = (451, 231)
(b) (n, E) = (3053, 1921)
(c) (n, E) = (37986733, 12371)
(d) (n, E) = (16394854313, 34578451)
11. Encrypted messages are often divided into blocks of n letters.
A message such as THE WORLD WONDERS WHY might be
encrypted as JIW OCFRJ LPOEVYQ IOC but sent as JIW OCF
RJL POE VYQ IOC. What are the advantages of using blocks of
n letters?
12. Find integers n, E, and X such that
XE X
(mod n).
104
13. Every person in the class should construct an RSA cryptosystem using primes that are 10 to 15 digits long. Hand in (n, E)
and an encoded message. Keep D secret. See if you can break one
anothers codes.
7.4
105
2. (Primality Testing) Recall Fermats Little Theorem from Chapter 6. Let p be prime with gcd(a, p) = 1. Then ap1 1 (mod p).
We can use Fermats Little Theorem as a screening test for primes.
For example, 15 cannot be prime since
2151 214 4
(mod 15).
(mod 17).
(mod n).
Which of the following numbers are primes and which are pseudoprimes?
(a) 342
(c) 601
(e) 771
(b) 811
(d) 561
(f) 631
7.5
[1]
[2]
Diffie, W. and Hellman, M. E. New Directions in Cryptography, IEEE Trans. Inform. Theory 22 (1976), 64454.
106
[3]
[4]
[5]
Hellman, M. E. The Mathematics of Public Key Cryptography, Scientific American 241(1979), 13039.
[6]
[7]
[8]
8
Algebraic Coding Theory
Coding theory is an application of algebra that has become increasingly important over the last several decades. When we transmit
data, we are concerned about sending a message over a channel
that could be affected by noise. We wish to be able to encode
and decode the information in a manner that will allow the detection, and possibly the correction, of errors caused by noise. This
situation arises in many areas of communications, including radio,
telephone, television, computer communications, and digital media
technology. Probability, combinatorics, group theory, linear algebra, and polynomial rings over finite fields all play important roles
in coding theory.
8.1
108
109
We will adopt the convention that bits are numbered left to right in binary
n-tuples.
110
By far the most common error-detecting codes used in computers are based on the addition of a parity bit. Typically, a computer stores information in m-tuples called words. Common word
lengths are 8, 16, and 32 bits. One bit in the word is set aside as
the parity check bit, and is not used to store information. This bit
is set to either 0 or 1, depending on the number of 1s in the word.
Adding a parity check bit allows the detection of all single errors because changing a single bit either increases or decreases the
number of 1s by one, and in either case the parity has been changed
from even to odd, so the new word is not a codeword. (We could
also construct an error detection scheme based on odd parity; that
is, we could set the parity check bit so that a codeword always has
an odd number of 1s.)
The even parity system is easy to implement, but has two drawbacks. First, multiple errors are not detectable. Suppose an A is
sent and the first and seventh bits are changed from 0 to 1. The
received word is a codeword, but will be decoded into a C instead
of an A. Second, we do not have the ability to correct errors. If
the 8-tuple (1001 1000) is received, we know that an error has
occurred, but we have no idea which bit has been changed. We
will now investigate a coding scheme that will not only allow us to
detect transmission errors but will actually correct the errors.
Transmitted
Codeword
000
111
000
0
3
001
1
2
Received Word
010 011 100 101
1
2
1
2
2
1
2
1
110
2
1
111
3
0
Maximum-Likelihood Decoding2
The coding scheme presented in Example 8.5 is not a complete
solution to the problem because it does not account for the pos2
111
0
q
q
112
Block Codes
If we are to develop efficient error-detecting and error-correcting
codes, we will need more sophisticated mathematical tools. Group
theory will allow faster methods of encoding and decoding messages. A code is an (n, m)-block code if the information that is
to be coded can be divided into blocks of m binary digits, each of
which can be encoded into n binary digits. More specifically, an
(n, m)-block code consists of an encoding function
n
E : Zm
2 Z2
113
Example 8.9. The even-parity coding system developed to detect single errors in ASCII characters is an (8, 7)-block code. The
encoding function is
E(x7 , x6 , . . . , x1 ) = (x8 , x7 , . . . , x1 ),
where x8 = x7 + x6 + + x1 with addition in Z2 .
Let x = (x1 , . . . , xn ) and y = (y1 , . . . , yn ) be binary n-tuples.
The Hamming distance or distance, d(x, y), between x and y is
the number of bits in which x and y differ. The distance between
two codewords is the minimum number of transmission errors required to change one codeword into the other. The minimum
distance for a code, dmin , is the minimum of all distances d(x, y),
where x and y are distinct codewords. The weight, w(x), of a binary codeword x is the number of 1s in x. Clearly, w(x) = d(x, 0),
where 0 = (00 0).
Example 8.10. Let x = (10101), y = (11010), and z = (00011)
be all of the codewords in some code C. Then we have the following
Hamming distances:
d(x, y) = 4,
d(x, z) = 3,
d(y, z) = 3.
The minimum distance for this code is 3. We also have the following
weights:
w(x) = 3,
w(y) = 3,
w(z) = 2.
The following proposition lists some basic properties about the
weight of a codeword and the distance between two codewords.
The proof is left as an exercise.
Proposition 8.11. Let x, y, and z be binary n-tuples. Then
1. w(x) = d(x, 0);
2. d(x, y) 0;
3. d(x, y) = 0 exactly when x = y;
4. d(x, y) = d(y, x);
5. d(x, y) d(x, z) + d(z, y).
The weights in a particular code are usually much easier to
compute than the Hamming distances between all codewords in
the code. If a code is set up carefully, we can use this fact to our
advantage.
Suppose that x = (1101) and y = (1100) are codewords in some
code. If we transmit (1101) and an error occurs in the rightmost
bit, then (1100) will be received. Since (1100) is a codeword, the
decoder will decode (1100) as the transmitted message. This code
114
0000
0011
0101
0110
1001
1010
1100
1111
0000
0
2
2
2
2
2
2
4
0011
2
0
2
2
2
2
4
2
0101
2
2
0
2
2
4
2
2
0110
2
2
2
0
4
2
2
2
1001
2
2
2
4
0
2
2
2
1010
2
2
4
2
2
0
2
2
1100
2
4
2
2
2
2
0
2
1111
4
2
2
2
2
2
2
0
115
00000
00111
11100
11011
00000
0
3
3
4
00111
3
0
4
3
11100
3
4
0
3
11011
4
3
3
0
Historical Note
Modern coding theory began in 1948 with C. Shannons paper,
A Mathematical Theory of Information [7]. This paper offered an
example of an algebraic code, and Shannons Theorem proclaimed
exactly how good codes could be expected to be. Richard Hamming
began working with linear codes at Bell Labs in the late 1940s and
early 1950s after becoming frustrated because the programs that
he was running could not recover from simple errors generated by
noise. Coding theory has grown tremendously in the past several
decades. The Theory of Error-Correcting Codes, by MacWilliams
and Sloane [5], published in 1977, already contained over 1500 references. Linear codes (Reed-Muller (32, 6)-block codes) were used
on NASAs Mariner space probes. More recent space probes such as
Voyager have used what are called convolution codes. Currently,
very active research is being done with Goppa codes, which are
heavily dependent on algebraic geometry.
8.2
Linear Codes
116
need to add additional structure to our codes. One way to accomplish this is to require that the code also be a group. A group
code is a code that is also a subgroup of Zn2 .
To check that a code is a group code, we need only verify one
thing. If we add any two elements in the code, the result must be
an n-tuple that is again in the code. It is not necessary to check
that the inverse of the n-tuple is in the code, since every codeword
is its own inverse, nor is it necessary to check that 0 is a codeword.
For instance,
(11000101) + (11000101) = (00000000).
Example 8.16. Suppose that we have a code that consists of the
following 7-tuples:
(0000000)
(0001111)
(0010101)
(0011010)
(0100110)
(0101001)
(0110011)
(0111100)
(1000011)
(1001100)
(1010110)
(1011001)
(1100101)
(1101010)
(1110000)
(1111111).
117
Linear Codes
From Example 8.16, it is now easy to check that the minimum
nonzero weight is 3; hence, the code does indeed detect and correct
all single errors. We have now reduced the problem of finding
good codes to that of generating group codes. One easy way to
generate group codes is to employ a bit of matrix theory.
Define the inner product of two binary n-tuples to be
x y = x1 y1 + + xn yn ,
where x = (x1 , x2 , . . . , xn )t and y = (y1 , y2 , . . . , yn )t are column
vectors.3 For example, if x = (011001)t and y = (110101)t , then
x y = 0. We can also look at an inner product as the product of
a row matrix with a column matrix; that is,
x y = xt y
(
= x1 x2
y1
)
y2
xn .
..
yn
= x1 y1 + x2 y2 + + xn yn .
Example 8.19. Suppose that the words to be encoded consist of
all binary 3-tuples and that our encoding scheme is even-parity. To
encode an arbitrary 3-tuple, we add a fourth bit to obtain an even
number of 1s. Notice that an arbitrary n-tuple x = (x1 , x2 , . . . , xn )t
has an even number of 1s exactly when x1 + x2 + + xn = 0;
hence, a 4-tuple x = (x1 , x2 , x3 , x4 )t has an even number of 1s if
x1 + x2 + x3 + x4 = 0, or
1
(
)
1
x 1 = xt 1 = x1 x2 x3 x4 = 0.
1
1
This example leads us to hope that there is a connection between
matrices and coding theory.
3
118
Let Mmn (Z2 ) denote the set of all m n matrices with entries
in Z2 . We do matrix operations as usual except that all our addition and multiplication operations occur in Z2 . Define the null
space of a matrix H Mmn (Z2 ) to be the set of all binary ntuples x such that Hx = 0. We denote the null space of a matrix
H by Null(H).
Example 8.20. Suppose that
0 1 0 1 0
H = 1 1 1 1 0 .
0 0 1 1 1
For a 5-tuple x = (x1 , x2 , x3 , x4 , x5 )t to be in the null space of H,
Hx = 0. Equivalently, the following system of equations must be
satisfied:
x2 + x4 = 0
x1 + x2 + x3 + x4 = 0
x3 + x4 + x5 = 0.
The set of binary 5-tuples satisfying these equations is
(00000)
(11110)
(10101)
(01011).
0 0 0 1 1
H = 0 1 1 0 1
1 0 1 0 0
by the matrix
1
1 .
1
Hx = 1 ,
1
119
8.3
a11
a21
.
..
am1
a12 a1,nm
a22 a2,nm
.. . .
..
.
.
.
am2 am,nm
1 0 0
0 1 0
. . .
.
.
.. .. . . ..
0 0 1
With each canonical parity-check matrix we can associate an n
(n m) standard generator matrix
(
G=
Inm
A
)
.
0 1 1
A = 1 1 0 ,
1 0 1
120
1
0
0
G=
0
1
1
0
0
0
1
and
0 1 1 1 0 0
H = 1 1 0 0 1 0 ,
1 0 1 0 0 1
respectively.
Observe that the rows in H represent the parity checks on
certain bit positions in a 6-tuple. The 1s in the identity matrix serve as parity checks for the 1s in the same row. If x =
(x1 , x2 , x3 , x4 , x5 , x6 ), then
x2 + x3 + x4
0 = Hx = x1 + x2 + x5 ,
x1 + x3 + x6
which yields a system of equations:
x2 + x3 + x4 = 0
x1 + x2 + x5 = 0
x1 + x3 + x6 = 0.
Here x4 serves as a check bit for x2 and x3 ; x5 is a check bit for x1
and x2 ; and x6 is a check bit for x1 and x3 . The identity matrix
keeps x4 , x5 , and x6 from having to check on each other. Hence,
x1 , x2 , and x3 can be arbitrary but x4 , x5 , and x6 must be chosen
to ensure parity. The null space of H is easily computed to be
(000000) (001101) (010110) (011011)
(100011) (101110) (110101) (111000).
An even easier way to compute the null space is with the generator
matrix G (Table 8.24).
121
Codeword Gx
000000
001101
010110
011011
100011
101110
110101
111000
122
hik gkj
k=1
nm
k=1
nm
hik gkj +
aik kj +
k=1
k=nm+1
n
hik gkj
i(mn),k akj
k=nm+1
= aij + aij
= 0,
where
{
ij =
1,
i=j
0,
i = j
123
1 1 1 0 0 1
1
1 0 0 1 0
0 = 0 .
1 1 0 0 1 0
1
0
We state this result in the following proposition and leave the
proof as an exercise.
Proposition 8.30. Let ei be the binary n-tuple with a 1 in the
ith coordinate and 0s elsewhere and suppose that H Mmn (Z2 ).
Then Hei is the ith column of the matrix H.
Theorem 8.31. Let H be an m n binary matrix. Then the null
space of H is a single error-detecting code if and only if no column
of H consists entirely of zeros.
Proof. Suppose that Null(H) is a single error-detecting code.
Then the minimum distance of the code must be at least 2. Since
the null space is a group code, it is sufficient to require that the
code contain no codewords of less than weight 2 other than the
zero codeword. That is, ei must not be a codeword for i = 1, . . . , n.
Since Hei is the ith column of H, the only way in which ei could
be in the null space of H would be if the ith column were all zeros,
which is impossible; hence, the code must have the capability to
detect at least single errors.
Conversely, suppose that no column of H is the zero column.
By Proposition 8.30, Hei = 0.
Example 8.32. If we consider
H1 = 1
1
the matrices
1 1 0 0
0 0 1 0
1 0 0 1
124
and
1 1 1 0 0
H2 = 1 0 0 0 0 ,
1 1 0 0 1
1 1 1 0
H = 1 0 0 1
1 1 0 0
and want to determine whether or not H is the canonical paritycheck matrix for an error-correcting code, it is necessary to make
certain that Null(H) does not contain any 4-tuples of weight 2.
That is, (1100), (1010), (1001), (0110), (0101), and (0011) must
not be in Null(H). The next theorem states that we can indeed
determine that the code generated by H is error-correcting by examining the columns of H. Notice in this example that not only
does H have no zero columns, but also that no two columns are
the same.
Theorem 8.34. Let H be a binary matrix. The null space of H
is a single error-correcting code if and only if H does not contain
any zero columns and no two columns of H are identical.
Proof. The n-tuple ei + ej has 1s in the ith and jth entries and
0s elsewhere, and w(ei + ej ) = 2 for i = j. Since
0 = H(ei + ej ) = Hei + Hej
can only occur if the ith and jth columns are identical, the null
space of H is a single error-correcting code.
Suppose now that we have a canonical parity-check matrix H
with three rows. Then we might ask how many more columns we
can add to the matrix and still have a null space that is a single
error-detecting and single error-correcting code. Since each column
has three entries, there are 23 = 8 possible distinct columns. We
cannot add the columns
0
0
1
0
0 , 0 , 1 , 0 .
1
0
0
0
125
So we can add as many as four columns and still maintain a minimum distance of 3.
In general, if H is an m n canonical parity-check matrix, then
there are n m information positions in each codeword. Each
column has m bits, so there are 2m possible distinct columns. It
is necessary that the columns 0, e1 , . . . , em be excluded, leaving
2m (1 + m) remaining columns for information if we are still to
maintain the ability not only to detect but also to correct single
errors.
8.4
Efficient Decoding
We are now at the stage where we are able to generate linear codes
that detect and correct errors fairly easily, but it is still a timeconsuming process to decode a received n-tuple and determine
which is the closest codeword, because the received n-tuple must
be compared to each possible codeword to determine the proper
decoding. This can be a serious impediment if the code is very
large.
Example 8.35. Given the binary
1 1
H= 0 1
1 0
matrix
1 0 0
0 1 0
0 0 1
126
1 0 1 1 0 0
H = 0 1 1 0 1 0
1 1 1 0 0 1
and suppose that the 6-tuples x = (111110)t , y = (111111)t , and
z = (010111)t have been received. Then
1
1
1
Hx = 1 , Hy = 1 , Hz = 0 .
1
0
0
Hence, x has an error in the third bit and z has an error in the
fourth bit. The transmitted codewords for x and z must have been
(110110) and (010011), respectively. The syndrome of y does not
occur in any of the columns of the matrix H, so multiple errors
must have occurred to produce y.
Coset Decoding
We can use group theory to obtain another way of decoding messages. A linear code C is a subgroup of Zn2 . Coset or standard
decoding uses the cosets of C in Zn2 to implement maximumlikelihood decoding. Suppose that C is an (n, m)-linear code. A
coset of C in Zn2 is written in the form x+C, where x Zn2 . By Lagranges Theorem (Theorem 6.10), there are 2nm distinct cosets
of C in Zn2 .
Example 8.39. Let C be the (5, 3)-linear code given by the paritycheck matrix
0 1 1 0 0
H = 1 0 0 1 0 .
1 1 0 0 1
The code consists of the codewords
(00000) (01101) (10011)
(11110).
127
Coset
(00000)
(10000)
(01000)
(00100)
(00010)
(00001)
(00111)
(00110)
(01101)
(11101)
(00101)
(01001)
(01111)
(01100)
(01010)
(01011)
(10011)
(00011)
(11011)
(10111)
(10001)
(10010)
(10100)
(10101)
(11110)
(01110)
(10110)
(11010)
(11100)
(11111)
(11001)
(11000)
Our task is to find out how knowing the cosets might help us
to decode a message. Suppose that x was the original codeword
sent and that r is the n-tuple received. If e is the transmission
error, then r = e + x or, equivalently, x = e + r. However, this
is exactly the statement that r is an element in the coset e + C.
In maximum-likelihood decoding we expect the error e to be as
small as possible; that is, e will have the least weight. An ntuple of least weight in a coset is called a coset leader. Once we
have determined a coset leader for each coset, the decoding process
becomes a task of calculating r + e to obtain x.
Example 8.41. In Table 8.40, notice that we have chosen a representative of the least possible weight for each coset. These representatives are coset leaders. Now suppose that r = (01111) is
the received word. To decode r, we find that it is in the coset
(00010) + C; hence, the originally transmitted codeword must have
been (01101) = (01111) + (00010).
128
Coset Leader
(00000)
(00001)
(00010)
(10000)
(00100)
(01000)
(00110)
(10100)
Hx = 1 .
1
Examining the decoding table, we determine that the coset leader
is (00010). It is now easy to decode the received codeword.
Given an (n, k)-block code, the question arises of whether or not
coset decoding is a manageable scheme. A decoding table requires
a list of cosets and syndromes, one for each of the 2nk cosets of
C. Suppose that we have a (32, 24)-block code. We have a huge
number of codewords, 224 , yet there are only 23224 = 28 = 256
cosets.
Sage Sage has a substantial repertoire of commands for coding
theory, including the ability to build many different families of
codes.
8.5
Exercises
8.5. EXERCISES
Information
Codeword
0
000
129
1
001
2
010
3
011
4
101
5
110
6
111
7
000
8
001
(1001)
(1010)
(1100)
(c) (01111)
(b) (11110101)
(d) (1011)
(b)
0 1 0 0 0
1 0 1 0 1
1 0 0 1 0
0
1
0
1
1
1
1
0
0
0
0
1
0
0
0
0
1
0
0
1
130
(c)
(d)
1
0
(
)
1 0 0 1 1
0 1 0 1 1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
0 1 0 0 1
H = 1 0 1 0 1 .
0 0 1 1 1
Decode the message
01111 10101
01110
00011
if possible.
10. Suppose that a 1000-bit binary message is transmitted. Assume that the probability of a single error is p and that the errors occurring in different bits are independent of one another. If
p = 0.01, what is the probability of more than one error occurring?
What is the probability of exactly two errors occurring? Repeat
this problem for p = 0.0001.
11. Which matrices are canonical parity-check matrices? For those
matrices that are canonical parity-check matrices, what are the
corresponding standard generator matrices? What are the errordetection and error-correction capabilities of the code generated by
each of these matrices?
(a)
0
1
(b)
0
1
1
0
0
0
1
1
1
1
0
1
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
1
(c)
(
)
1 1 1 0
1 0 0 1
(d)
1
0
0
1
0
1
0
1
1
1
1
0
0
0
0
1
0
0
0
0
1
0
0
1
8.5. EXERCISES
131
12. List all possible syndromes for the codes generated by each of
the matrices in Exercise 8.5.11.
13. Let
0 1 1 1 1
H = 0 0 0 1 1 .
1 0 1 0 1
(c)
(
)
1 0 0 1 1
0 1 0 1 1
0 1 0 0 0
1 0 1 0 1
1 0 0 1 0
(b)
(d)
0
1
0
1
1
1
1
0
0
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
0
132
1 1 1 0 0
0 0 1 0 1 .
1 0 0 1 0
(b) Show that C is an (n, n k)-linear code.
133
0 0 0 1 1 1
H = 0 1 1 0 0 1
1 0 1 0 1 0
134
8.7
[1]
[2]
[3]
[4]
[5]
MacWilliams, F. J. and Sloane, N. J. A. The Theory of ErrorCorrecting Codes. North-Holland Mathematical Library, 16,
Elsevier, Amsterdam, 1983.
[6]
[7]
Shannon, C. E. A Mathematical Theory of Communication, Bell System Technical Journal 27(1948), 379423, 623
56.
[8]
[9]
2nd ed.
9
Isomorphisms
9.1
Two groups (G, ) and (H, ) are isomorphic if there exists a oneto-one and onto map : G H such that the group operation is
preserved; that is,
(a b) = (a) (b)
for all a and b in G. If G is isomorphic to H, we write G
= H.
The map is called an isomorphism.
i, define a map : Z4 i
Example 9.1. To show that Z4 =
n
by (n) = i . We must show that is bijective and preserves the
group operation. The map is one-to-one and onto because
(0) = 1
(1) = i
(2) = 1
(3) = i.
Since
(m + n) = im+n = im in = (m)(n),
the group operation is preserved.
Example 9.2. We can define an isomorphism from the additive
group of real numbers (R, +) to the multiplicative group of positive
real numbers (R+ , ) with the exponential map; that is,
(x + y) = ex+y = ex ey = (x)(y).
Of course, we must still show that is one-to-one and onto, but
this can be determined using calculus.
135
136
CHAPTER 9. ISOMORPHISMS
and (n) = b.
However,
ab = (m)(n) = (m + n) = (n + m) = (n)(m) = ba,
which contradicts the fact that a and b do not commute.
Theorem 9.6. Let : G H be an isomorphism of two groups.
Then the following statements are true.
1. 1 : H G is an isomorphism.
137
2. |G| = |H|.
3. If G is abelian, then H is abelian.
4. If G is cyclic, then H is cyclic.
5. If G has a subgroup of order n, then H has a subgroup of
order n.
Proof. Assertions (1) and (2) follow from the fact that is a
bijection. We will prove (3) here and leave the remainder of the
theorem to be proved in the exercises.
(3) Suppose that h1 and h2 are elements of H. Since is
onto, there exist elements g1 , g2 G such that (g1 ) = h1 and
(g2 ) = h2 . Therefore,
h1 h2 = (g1 )(g2 ) = (g1 g2 ) = (g2 g1 ) = (g2 )(g1 ) = h2 h1 .
138
CHAPTER 9. ISOMORPHISMS
Cayleys Theorem
Cayley proved that if G is a group, it is isomorphic to a group
of permutations on some set; hence, every group is a permutation
group. Cayleys Theorem is what we call a representation theorem.
The aim of representation theory is to find an isomorphism of some
group G that we wish to study into a group that we know a great
deal about, such as a group of permutations or matrices.
Example 9.11. Consider the group Z3 . The Cayley table for Z3
is as follows.
+
0
1
2
0
0
1
2
1
1
2
0
2
2
0
1
139
140
9.2
CHAPTER 9. ISOMORPHISMS
Direct Products
141
we have used only two groups to build a new group. The direct
product
n
Gi = G1 G2 Gn
i=1
(0, 1),
(0, 2),
(1, 0),
(1, 1),
(1, 2).
142
CHAPTER 9. ISOMORPHISMS
Zni
= Zn1 nk
i=1
143
G = HK = {hk : h H, k K};
H K = {e};
hk = kh for all k K and h H.
Then G is the internal direct product of H and K.
Example 9.24. The group U (8) is the internal direct product of
H = {1, 3}
Example 9.25. The dihedral group D6 is an internal direct product of its two subgroups
H = {id, r3 } and
K = {id, r2 , r4 , s, r2 s, r4 s}.
144
CHAPTER 9. ISOMORPHISMS
Example 9.28. The group Z6 is an internal direct product isomorphic to {0, 2, 4} {0, 3}.
We can extend the definition of an internal direct product of G
to a collection of subgroups H1 , H2 , . . . , Hn of G, by requiring that
G = H1 H2 Hn = {h1 h2 hn : hi Hi };
Hi j=i Hj = {e};
hi hj = hj hi for all hi Hi and hj Hj .
We will leave the proof of the following theorem as an exercise.
Theorem 9.29. Let G be the internal direct product
of subgroups
Hi , where i = 1, 2, . . . , n. Then G is isomorphic to i Hi .
Sage Sage can quickly determine if two permutation groups are
isomorphic, even though this should, in theory, be a very difficult
computation.
9.3
Exercises
1. Prove that Z
= nZ for n = 0.
2. Prove that C is isomorphic to the subgroup of GL2 (R) consisting of matrices of the form
)
(
a b
.
b a
3. Prove or disprove: U (8)
= Z4 .
4. Prove that U (8) is isomorphic to the group of matrices
)
) (
) (
) (
(
1 0
1 0
1 0
1 0
,
.
,
,
0 1
0 1
0 1
0 1
5. Show that U (5) is isomorphic to U (10), but U (12) is not.
6. Show that the nth roots of unity are isomorphic to Zn .
7. Show that any cyclic group of order n is isomorphic to Zn .
8. Prove that Q is not isomorphic to Z.
9. Let G = R \ {1} and define a binary operation on G by
a b = a + b + ab.
Prove that G is a group under this operation. Show that (G, ) is
isomorphic to the multiplicative group of nonzero real numbers.
9.3. EXERCISES
1 0 0
1
0 1 0 0
0 0 1
0
0 0 1
0
1 0 0 0
0 1 0
1
145
0 0
0 1
1 0
0 1
1 0
0 0
0
1
0
0
0
1
1 0
0 0
0 1
1 0
0 1
0 0
0
0 1
A=
and
B
=
0 1
1 0
generate a multiplicative group isomorphic to Dn .
14. Show that the set of all matrices of the form
(
)
1 k
,
0 1
is a group isomorphic to Dn , where all entries in the matrix are in
Zn .
15. List all of the elements of Z4 Z2 .
16. Find the order of each of the following elements.
(a) (3, 4) in Z4 Z6
(b) (6, 15, 4) in Z30 Z45 Z24
(c) (5, 10, 15) in Z25 Z25 Z25
(d) (8, 8, 8) in Z10 Z24 Z80
17. Prove that D4 cannot be the internal direct product of two of
its proper subgroups.
18. Prove that the subgroup of Q consisting of elements of the
form 2m 3n for m, n Z is an internal direct product isomorphic to
Z Z.
19. Prove that S3 Z2 is isomorphic to D6 . Can you make a
conjecture about D2n ? Prove your conjecture.
146
CHAPTER 9. ISOMORPHISMS
9.3. EXERCISES
147
Zni
= Zn1 nk
i=1
148
CHAPTER 9. ISOMORPHISMS
10
Normal Subgroups and
Factor Groups
Factor Groups
If N is a normal subgroup of a group G, then the cosets of N in
G form a group G/N under the operation (aN )(bN ) = abN . This
group is called the factor or quotient group of G and N . Our
first task is to prove that G/N is indeed a group.
Theorem 10.4. Let N be a normal subgroup of a group G. The
cosets of N in G form a group G/N of order [G : N ].
Proof. The group operation on G/N is (aN )(bN ) = abN . This
operation must be shown to be well-defined; that is, group multiplication must be independent of the choice of coset representative.
Let aN = bN and cN = dN . We must show that
(aN )(cN ) = acN = bdN = (bN )(dN ).
Then a = bn1 and c = dn2 for some n1 and n2 in N . Hence,
acN = bn1 dn2 N
= bn1 dN
= bn1 N d
= bN d
= bdN.
The remainder of the theorem is easy: eN = N is the identity and
g 1 N is the inverse of gN . The order of G/N is, of course, the
number of cosets of N in G.
151
N
(12)N
N
N
(12)N
(12)N
(12)N
N
0 + 3Z
0 + 3Z
1 + 3Z
2 + 3Z
1 + 3Z
1 + 3Z
2 + 3Z
0 + 3Z
2 + 3Z
2 + 3Z
0 + 3Z
1 + 3Z
10.2
1 (a1 a2 a4 )(a1 a2 a4 )1 N
(a1 a2 a4 )(a1 a2 a4 )1 N.
So
1 (a1 a2 a4 )(a1 a2 a4 )1 = [ (a1 a2 a3 )(a4 a5 a6 )]1 (a1 a2 a4 ) (a1 a2 a3 )(a4 a5 a6 )(a1 a2 a4 )1
= (a4 a6 a5 )(a1 a3 a2 ) 1 (a1 a2 a4 ) (a1 a2 a3 )(a4 a5 a6 )(a1 a4 a2 )
= (a4 a6 a5 )(a1 a3 a2 )(a1 a2 a4 )(a1 a2 a3 )(a4 a5 a6 )(a1 a4 a2 )
= (a1 a4 a2 a6 a3 ).
So N contains a disjoint cycle of length greater than 3, and we can
apply the previous case.
Suppose N contains a disjoint product of the form = (a1 a2 a3 ),
where is the product of disjoint 2-cycles. Since N , 2 N ,
and
2 = (a1 a2 a3 ) (a1 a2 a3 )
= (a1 a3 a2 ).
So N contains a 3-cycle.
The only remaining possible case is a disjoint product of the
form
= (a1 a2 )(a3 a4 ),
where is the product of an even number of disjoint 2-cycles. But
1 (a1 a2 a3 )(a1 a2 a3 )1
is in N since (a1 a2 a3 )(a1 a2 a3 )1 is in N ; and so
1 (a1 a2 a3 )(a1 a2 a3 )1 = 1 (a1 a2 )(a3 a4 )(a1 a2 a3 ) (a1 a2 )(a3 a4 )(a1 a2 a3 )1
= (a1 a3 )(a2 a4 ).
Since n 5, we can find b {1, 2, . . . , n} such that b = a1 , a2 , a3 , a4 .
Let = (a1 a3 b). Then
1 (a1 a3 )(a2 a4 )(a1 a3 )(a2 a4 ) N
and
1 (a1 a3 )(a2 a4 )(a1 a3 )(a2 a4 ) = (a1 ba3 )(a1 a3 )(a2 a4 )(a1 a3 b)(a1 a3 )(a2 a4 )
= (a1 a3 b).
Therefore, N contains a 3-cycle. This completes the proof of the
lemma.
10.3. EXERCISES
155
10.3
Exercises
10.3. EXERCISES
157
Show that C(g) is a subgroup of G. If g generates a normal subgroup of G, prove that C(g) is normal in G.
13. Recall that the center of a group G is the set
Z(G) = {x G : xg = gx for all g G}.
(a) Calculate the center of S3 .
(b) Calculate the center of GL2 (R).
(c) Show that the center of any group G is a normal subgroup of
G.
(d) If G/Z(G) is cyclic, show that G is abelian.
14. Let G be a group and let G = aba1 b1 ; that is, G is
the subgroup of all finite products of elements in G of the form
aba1 b1 . The subgroup G is called the commutator subgroup
of G.
(a) Show that G is a normal subgroup of G.
(b) Let N be a normal subgroup of G. Prove that G/N is abelian
if and only if N contains the commutator subgroup of G.
11
Homomorphisms
One of the basic ideas of algebra is the concept of a homomorphism, a natural generalization of an isomorphism. If we relax the
requirement that an isomorphism of groups be bijective, we have a
homomorphism.
11.1
Group Homomorphisms
159
160
11.2
161
Although it is not evident at first, factor groups correspond exactly to homomorphic images, and we can use factor groups to
study homomorphisms. We already know that with every group
homomorphism : G H we can associate a normal subgroup of
G, ker . The converse is also true; that is, very normal subgroup
of a group G gives rise to homomorphism of groups.
Let H be a normal subgroup of G. Define the natural or
canonical homomorphism
: G G/H
by
(g) = gH.
This is indeed a homomorphism, since
(g1 g2 ) = g1 g2 H = g1 Hg2 H = (g1 )(g2 ).
The kernel of this homomorphism is H. The following theorems
describe the relationships between group homomorphisms, normal
subgroups, and factor groups.
Theorem 11.10 (First Isomorphism Theorem). If : G H is
a group homomorphism with K = ker , then K is normal in G.
Let : G G/K be the canonical homomorphism. Then there
exists a unique isomorphism : G/K (G) such that = .
Proof. We already know that K is normal in G. Define :
G/K (G) by (gK) = (g). We first show that is a welldefined map. If g1 K = g2 K, then for some k K, g1 k = g2 ;
consequently,
(g1 K) = (g1 ) = (g1 )(k) = (g1 k) = (g2 ) = (g2 K).
Thus, does not depend on the choice of coset representatives and
the map : G/K (G) is uniquely defined since = . We
must also show that is a homomorphism, but
(g1 Kg2 K) = (g1 g2 K)
= (g1 g2 )
= (g1 )(g2 )
= (g1 K)(g2 K).
Clearly, is onto (G). To show that is one-to-one, suppose
that (g1 K) = (g2 K). Then (g1 ) = (g2 ). This implies that
(g11 g2 ) = e, or g11 g2 is in the kernel of ; hence, g11 g2 K = K;
that is, g1 K = g2 K.
162
Mathematicians often use diagrams called commutative diagrams to describe such theorems. The following diagram commutes since = .
G/K
163
G/N
H/N
164
11.3
Exercises
)
1 0
a 1
=a+d
c d
(d) : GL2 (R) R defined by
((
))
a b
= ad bc
c d
(e) : M2 (R) R defined by
((
))
a b
= b,
c d
where M2 (R) is the additive group of 2 2 matrices with
entries in R.
11.3. EXERCISES
165
166
11.4
1. Let Aut(G) be the set of all automorphisms of G; that is, isomorphisms from G to itself. Prove this set forms a group and is a
subgroup of the group of permutations of G; that is, Aut(G) SG .
2. An inner automorphism of G,
ig : G G,
is defined by the map
ig (x) = gxg 1 ,
for g G. Show that ig Aut(G).
3. The set of all inner automorphisms is denoted by Inn(G). Show
that Inn(G) is a subgroup of Aut(G).
4. Find an automorphism of a group G that is not an inner automorphism.
5. Let G be a group and ig be an inner automorphism of G, and
define a map
G Aut(G)
by
g 7 ig .
Prove that this map is a homomorphism with image Inn(G) and
kernel Z(G). Use this result to conclude that
G/Z(G)
= Inn(G).
6. Compute Aut(S3 ) and Inn(S3 ). Do the same thing for D4 .
7. Find all of the homomorphisms : Z Z. What is Aut(Z)?
167
12
Matrix Groups and
Symmetry
12.1
Matrix Groups
A= .
..
..
..
..
.
.
.
am1 am2 amn
168
169
and
Ax = A(x),
x1
x2
x = . .
..
xn
=
a1k xk , . . . ,
amk xk
k=1
k=1
= Ax.
Example 12.1. If we let T : R2 R2 be the map given by
T (x1 , x2 ) = (2x1 + 5x2 , 4x1 + 3x2 ),
the axioms that T must satisfy to be a linear transformation are
easily verified. The column vectors T e1 = (2, 4)t and T e2 =
(5, 3)t tell us that T is given by the matrix
(
)
2 5
A=
.
4 3
170
1 0 0
0 1 0
I = . . .
.
.. .. . . ..
0 0 1
(
=
)
3 1
.
5 2
171
1
=
ad bc
)
d b
.
c a
(
=
)
d b
.
c a
y
(1, 1)
(0, 1)
(1, 0)
(1, 0)
172
(
)
(
)
1/ 2
0 1/2
3/5 4/5
1/2 3/2 , 1/ 6 2/ 6 1/ 6 .
,
4/5 3/5
3/2
1/2
1/ 3
1/ 3 1/ 3
There is a more geometric way of viewing the group O(n). The
orthogonal matrices are exactly those matrices that preserve the
length of vectors. We can define the length of a vector using the
Euclidean inner product, or dot product, of two vectors. The
Euclidean inner product of two vectors x = (x1 , . . . , xn )t and y =
(y1 , . . . , yn )t is
y1
y2
x, y = xt y = (x1 , x2 , . . . , xn ) . = x1 y1 + + xn yn .
..
yn
We define the length of a vector x = (x1 , . . . , xn )t to be
x = x, x = x21 + + x2n .
Associated with the notion of the length of a vector is the idea of
the distance between two vectors. We define the distance between
two vectors x and y to be x y. We leave as an exercise the
proof of the following proposition about the properties of Euclidean
inner products.
Proposition 12.6. Let x, y, and w be vectors in Rn and R.
Then
1. x, y = y, x.
2. x, y + w = x, y + x, w.
3. x, y = x, y = x, y.
4. x, x 0 with equality exactly when x = 0.
5. If x, y = 0 for all x in Rn , then y = 0.
Example 12.7. The vector x = (3, 4)t has length
We can also see that the orthogonal matrix
(
)
3/5 4/5
A=
4/5 3/5
32 + 42 = 5.
173
174
]
1[
x + y2 x2 y2 .
2
Observe that
]
1[
Ax + Ay2 Ax2 Ay2
2
]
1[
=
A(x + y)2 Ax2 Ay2
2
]
1[
x + y2 x2 y2
=
2
= x, y.
Ax, Ay =
y
(sin , cos )
(cos , sin )
(a, b)
x
(a, b)
175
y
x+y
x
x
176
12.2
Symmetry
An isometry or rigid motion in Rn is a distance-preserving function f from Rn to Rn . This means that f must satisfy
f (x) f (y) = x y
for all x, y Rn . It is not difficult to show that f must be a oneto-one map. By Theorem 12.8, any element in O(n) is an isometry
on Rn ; however, O(n) does not include all possible isometries on
Rn . Translation by a vector x, Ty (x) = x + y is also an isometry
(Figure 12.11); however, T cannot be in O(n) since it is not a linear
map.
We are mostly interested in isometries in R2 . In fact, the only
isometries in R2 are rotations and reflections about the origin,
translations, and combinations of the two. For example, a glide
reflection is a translation followed by a reflection (Figure 12.12).
In Rn all isometries are given in the same manner. The proof is
very easy to generalize.
y
x
x
x
T (x)
12.2. SYMMETRY
177
Consequently,
f (x), f (y) = x, y.
Now let e1 and e2 be (1, 0)t and (0, 1)t , respectively. If
x = (x1 , x2 ) = x1 e1 + x2 e2 ,
then
f (x) = f (x), f (e1 )f (e1 )+f (x), f (e2 )f (e2 ) = x1 f (e1 )+x2 f (e2 ).
The linearity of f easily follows.
For any arbitrary isometry, f , Tx f will fix the origin for some
vector x in R2 ; hence, Tx f (y) = Ay for some matrix A O(2).
Consequently, f (y) = Ay + x. Given the isometries
f (y) = Ay + x1
g(y) = By + x2 ,
their composition is
f (g(y)) = f (By + x2 ) = ABy + Ax2 + x1 .
This last computation allows us to identify the group of isometries
on R2 with E(2).
Theorem 12.14. The group of isometries on R2 is the Euclidean
group, E(2).
A symmetry group in Rn is a subgroup of the group of isometries on Rn that fixes a set of points X R2 . It is important to
realize that the symmetry group of X depends both on Rn and on
X. For example, the symmetry group of the origin in R1 is Z2 , but
the symmetry group of the origin in R2 is O(2).
Theorem 12.15. The only finite symmetry groups in R2 are Zn
and Dn .
Proof. Any finite symmetry group G in R2 must be a finite subgroup of O(2); otherwise, G would have an element in E(2) of the
form (A, x), where x = 0. Such an element must have infinite
order.
By Example 12.10, elements in O(2) are either rotations of the
form
(
)
cos sin
R =
sin cos
or reflections of the form
(
)(
) (
)
cos sin
1 0
cos sin
T =
=
.
sin cos
0 1
sin cos
178
12.2. SYMMETRY
179
180
(1, 1)
(1, 1)
(2, 0)
(1, 1)
12.2. SYMMETRY
181
Theorem 12.20. The point group in the wallpaper groups is isomorphic to Zn or Dn , where n = 1, 2, 3, 4, 6.
To answer the question of how the point groups and the translation groups can be combined, we must look at the different types
of lattices. Lattices can be classified by the structure of a single
lattice cell. The possible cell shapes are parallelogram, rectangular, square, rhombic, and hexagonal (Figure 12.21). The wallpaper
groups can now be classified according to the types of reflections
that occur in each group: these are ordinarily reflections, glide
reflections, both, or none.
Rectangular
Square
Rhombic
Parallelogram
Hexagonal
182
Notation and
Space Groups
p1
p2
p3
p4
p6
pm
pg
cm
pmm
pmg
pgg
c2mm
p3m1, p31m
p4m, p4g
p6m
Point Group
Z1
Z2
Z3
Z4
Z6
D1
D1
D1
D2
D2
D2
D2
D3
D4
D6
Lattice Type
parallelogram
parallelogram
hexagonal
square
hexagonal
rectangular
rectangular
rhombic
rectangular
rectangular
rectangular
rhombic
hexagonal
square
hexagonal
Reflections or
Glide Reflections?
none
none
none
none
none
reflections
glide reflections
both
reflections
glide reflections
both
both
both
both
both
p4m
p4g
12.3. EXERCISES
183
Historical Note
12.3
Exercises
]
1[
x + y2 x2 y2 .
2
(c)
4/ 5
0 3/5
3/ 5 0 4/ 5
0
1
0
)
(
1/2 1/ 2
1/ 2 1/ 2
(d)
(b)
)
1/ 5 2/5
2/ 5 1/ 5
184
(a)
(c)
(b)
Figure 12.25
185
Figure 12.26
12.4
186
[1]
Coxeter, H. M. and Moser, W. O. J. Generators and Relations for Discrete Groups, 3rd ed. Springer-Verlag, New
York, 1972.
[2]
[3]
Hiller, H. Crystallography and Cohomology of Groups, American Mathematical Monthly 93 (1986), 76579.
[4]
[5]
[6]
[7]
[8]
[9]
13
The Structure of Groups
13.1
188
then G is generated by the set {gi : i I}. In this case the gi s are
said to be the generators of G. If there is a finite set {gi : i I}
that generates G, then G is finitely generated.
Example 13.1. Obviously, all finite groups are finitely generated.
For example, the group S3 is generated by the permutations (12)
and (123). The group Z Zn is an infinite group but is finitely
generated by {(1, 0), (0, 1)}.
Example 13.2. Not all groups are finitely generated. Consider
the rational numbers Q under the operation of addition. Suppose
that Q is finitely generated with generators p1 /q1 , . . . , pn /qn , where
each pi /qi is a fraction expressed in its lowest terms. Let p be some
prime that does not divide any of the denominators q1 , . . . , qn . We
claim that 1/p cannot be in the subgroup of Q that is generated by
p1 /q1 , . . . , pn /qn , since p does not divide the denominator of any
element in this subgroup. This fact is easy to see since the sum of
any two generators is
pi /qi + pj /qj = (pi qj + pj qi )/(qi qj ).
Theorem 13.3. Let H be the subgroup of a group G that is generated by {gi G : i I}. Then h H exactly when it is a product
of the form
h = gi11 ginn ,
where the gik s are not necessarily distinct.
Proof. Let K be the set of all products of the form gi11 ginn ,
where the gik s are not necessarily distinct. Certainly K is a subset
of H. We need only show that K is a subgroup of G. If this is the
case, then K = H, since H is the smallest subgroup containing all
the gi s.
Clearly, the set K is closed under the group operation. Since
gi0 = 1, the identity is in K. It remains to show that the inverse of
an element g = gik11 giknn in K must also be in K. However,
n
1
g 1 = (gik11 giknn )1 = (gik
gik
).
n
1
189
190
(g r )p
= (hp )p
m1
= hp = e,
H = (gH)p
= gp
m1
H;
191
m1
hence, g p
must be in g H = {e}, which contradicts the
fact that the order of g is pm . Therefore, gH must have maximal
order in G/H. By the Correspondence Theorem and our induction
hypothesis,
G/H
= gH K/H
for some subgroup K of G containing H. We claim that g K =
{e}. If b g K, then bH gH K/H = {H} and b g
H = {e}. It follows that G = gK implies that G
= g K.
The proof of the Fundamental Theorem of Finite Abelian Groups
follows very quickly from Lemma 13.7. Suppose that G is a finite
abelian group and let g be an element of maximal order in G. If
g = G, then we are done; otherwise, G
= Z|g| H for some subgroup H contained in G by the lemma. Since |H| < |G|, we can
apply mathematical induction.
We now state the more general theorem for all finitely generated
abelian groups. The proof of this theorem can be found in any of
the references at the end of this chapter.
Theorem 13.8 (The Fundamental Theorem of Finitely Generated Abelian Groups). Every finitely generated abelian group G is
isomorphic to a direct product of cyclic groups of the form
Zp1 Zp2 Zpnn Z Z,
1
13.2
Solvable Groups
192
A subnormal (normal) series {Kj } is a refinement of a subnormal (normal) series {Hi } if {Hi } {Kj }. That is, each Hi
is one of the Kj .
Example 13.11. The series
Z 3Z 9Z 45Z 90Z 180Z {0}
is a refinement of the series
Z 9Z 45Z 180Z {0}.
The best way to study a subnormal or normal series of subgroups, {Hi } of G, is actually to study the factor groups Hi+1 /Hi .
We say that two subnormal (normal) series {Hi } and {Kj } of a
group G are isomorphic if there is a one-to-one correspondence
between the collections of factor groups {Hi+1 /Hi } and {Kj+1 /Kj }.
Example 13.12. The two normal series
Z60 3 15 {0}
Z60 4 20 {0}
of the group Z60 are isomorphic since
Z60 /3
= 20/{0}
= Z3
3/15
= 4/20
= Z5
15/{0}
= Z60 /4
= Z4 .
A subnormal series {Hi } of a group G is a composition series
if all the factor groups are simple; that is, if none of the factor
groups of the series contains a normal subgroup. A normal series
{Hi } of G is a principal series if all the factor groups are simple.
Example 13.13. The group Z60 has a composition series
Z60 3 15 30 {0}
with factor groups
Z60 /3
= Z3
3/15
= Z5
15/30
= Z2
30/{0}
= Z2 .
Since Z60 is an abelian group, this series is automatically a principal
series. Notice that a composition series need not be unique. The
series
Z60 2 4 20 {0}
is also a composition series.
193
194
Km1 )/Hi is either Hi+1 /Hi or Hi /Hi . That is, Hi (Hi+1 Km1 )
must be either Hi or Hi+1 . Removing any nonproper inclusions
from the series
Hn1 Hn1 Km1 H0 Km1 = {e},
we have a composition series for Hn1 . Our induction hypothesis
says that this series must be equivalent to the composition series
Hn1 H1 H0 = {e}.
Hence, the composition series
G = Hn Hn1 H1 H0 = {e}
and
G = Hn Hn1 Hn1 Km1 H0 Km1 = {e}
are equivalent. If Hn1 = Km1 , then the composition series {Hi }
and {Kj } are equivalent and we are done; otherwise, Hn1 Km1
is a normal subgroup of G properly containing Hn1 . In this case
Hn1 Km1 = G and we can apply the Second Isomorphism Theorem once again; that is,
Km1 /(Km1 Hn1 )
= (Hn1 Km1 )/Hn1 = G/Hn1 .
Therefore,
G = Hn Hn1 Hn1 Km1 H0 Km1 = {e}
and
G = Km Km1 Km1 Hn1 K0 Hn1 = {e}
are equivalent and the proof of the theorem is complete.
A group G is solvable if it has a subnormal series {Hi } such
that all of the factor groups Hi+1 /Hi are abelian. Solvable groups
will play a fundamental role when we study Galois theory and the
solution of polynomial equations.
Example 13.17. The group S4 is solvable since
S4 A4 {(1), (12)(34), (13)(24), (14)(23)} {(1)}
has abelian factor groups; however, for n 5 the series
Sn An {(1)}
is a composition series for Sn with a nonabelian factor group.
Therefore, Sn is not a solvable group for n 5.
13.3. EXERCISES
195
13.3
Exercises
(e) S3 Z4
(b) Z48
(f) S4
(g) Sn , n 5
(d) D4
(h) Q
196
197
(c) H (H K)/H (H K )
= K (H K)/K (H K)
= (H
K)/(H K)(H K ).
23. (Schreiers Theorem) Use the Zassenhaus Lemma to prove
that two subnormal (normal) series of a group G have isomorphic
refinements.
24. Use Schreiers Theorem to prove the Jordan-Hlder Theorem.
13.4
Programming Exercises
13.5
[1]
[2]
[3]
14
Group Actions
14.1
199
200
201
14.2
|Oxi |,
i=k
202
Now consider the special case in which G acts on itself by conjugation, (g, x) 7 gxg 1 . The center of G,
Z(G) = {x : xg = gx for all g G},
is the set of points that are fixed by conjugation. The nontrivial
orbits of the action are called the conjugacy classes of G. If
x1 , . . . , xk are representatives from each of the nontrivial conjugacy
classes of G and |Ox1 | = n1 , . . . , |Oxk | = nk , then
|G| = |Z(G)| + n1 + + nk .
The stabilizer subgroups of each of the xi s, C(xi ) = {g G :
gxi = xi g}, are called the centralizer subgroups of the xi s.
From Theorem 14.11, we obtain the class equation:
|G| = |Z(G)| + [G : C(x1 )] + + [G : C(xk )].
One of the consequences of the class equation is that the order of
each conjugacy class must divide the order of G.
Example 14.12. It is easy to check that the conjugacy classes in
S3 are the following:
{(1)},
{(123), (132)},
{(1432), (1234)},
{(12)(34), (14)(23)}.
203
therefore, there are three conjugacy classes. The problem of finding the number of such partitions for any positive integer n is what
computer scientists call NP-complete. This effectively means
that the problem cannot be solved for a large n because the computations would be too time-consuming for even the largest computer.
Theorem 14.15. Let G be a group of order pn where p is prime.
Then G has a nontrivial center.
14.3
204
1
|Xg |.
|G|
gG
205
|Xg |.
gG
|Gx |;
hence,
gG |Xg |
xX
xX
yOx
|Xg | =
|Gx | = k |G|.
gG
xX
A Geometric Example
Before we apply Burnsides Theorem to switching-theory problems,
let us examine the number of ways in which the vertices of a square
can be colored black or white. Notice that we can sometimes obtain equivalent colorings by simply applying a rigid motion to the
square. For instance, as we have pointed out, if we color one of
the vertices black and the remaining three white, it does not matter which vertex was colored black since a rotation will give an
equivalent coloring.
The symmetry group of a square, D4 , is given by the following
permutations:
(1)
(13)
(24)
(1432)
(1234)
(12)(34)
(14)(23)
(13)(24)
206
207
e
Proposition 14.21. Let G be a permutation group of X and X
the set of functions from X to Y . Then there exists a permutation
e acting on X,
e where
e is defined by
group G
eG
e(f ) = f for
e
G and f X. Furthermore, if n is the number of cycles in the
e | = |Y |n .
cycle decomposition of , then |X
e Clearly, f is also in X.
e Suppose
Proof. Let G and f X.
that g is another function from X to Y such that
e(f ) =
e(g).
Then for each x X,
f ((x)) =
e(f )(x) =
e(g)(x) = g((x)).
Since is a permutation of X, every element x in X is the image
of some x in X under ; hence, f and g agree on all elements of
X. Therefore, f = g and
e is injective. The map 7
e is onto,
since the two sets are the same size.
Suppose that is a permutation of X with cycle decomposition
e must have the same value on each
= 1 2 n . Any f in X
cycle of . Since there are n cycles and |Y | possible values for each
e | = |Y |n .
cycle, |X
Example 14.22. Let X = {1, 2, . . . , 7} and suppose that Y =
{A, B, C}. If g is the permutation of X given by (13)(245) =
eg must have the same
(13)(245)(6)(7), then n = 4. Any f X
value on each cycle in g. There are |Y | = 3 such choices for any
eg | = 34 = 81.
value, so |X
Example 14.23. Suppose that we wish to color the vertices of a
square using four different colors. By Proposition 14.21, we can
immediately decide that there are
1 4
(4 + 41 + 42 + 41 + 42 + 42 + 43 + 43 ) = 55
8
possible ways.
Switching Functions
In switching theory we are concerned with the design of electronic
circuits with binary inputs and outputs. The simplest of these
circuits is a switching function that has n inputs and a single output
(Figure 14.24). Large electronic circuits can often be constructed
by combining smaller modules of this kind. The inherent problem
here is that even for a simple circuit a large number of different
switching functions can be constructed. With only four inputs
and a single output, we can construct 65,536 different switching
functions. However, we can often replace one switching function
with another merely by permuting the input leads to the circuit
(Figure 14.25).
208
f (x1 , x2 , . . . , xn )
a
f
f (a, b)
f (b, a) = g(a, b)
b
Figure 14.25: A switching function of two variables
f2 f4
f3 f5
f10 f12
f11 f13 .
0
1
0
1
f0
0
0
0
0
f1
0
0
0
1
f2
0
0
1
0
f8
1
0
0
0
f9
1
0
0
1
f10
1
0
1
0
Outputs
f3
f4
f5
0
0
0
0
1
1
1
0
0
1
0
1
Outputs
f11 f12 f13
1
1
1
0
1
1
1
0
0
1
0
1
209
f6
0
1
1
0
f7
0
1
1
1
f14
1
1
1
0
f15
1
1
1
1
(0, 0, 0) 7 (0, 0, 0)
(0, 0, 1) 7 (0, 1, 0)
(0, 1, 0) 7 (1, 0, 0)
..
.
(1, 1, 0) 7 (1, 0, 1)
(1, 1, 1) 7 (1, 1, 1).
210
follows:
(0, . . . , 0, 1) 7 0
(0, . . . , 1, 0) 7 1
(0, . . . , 1, 1) 7 2
..
.
(1, . . . , 1, 1) 7 2n 1.
Now let us consider a circuit with four input variables and a single
output. Suppose that we can permute the leads of any circuit
according to the following permutation group:
(a)
(ac) (bd)
(adcb)
(ac)(bd).
Number
of Cycles
16
12
12
6
6
10
10
10
14.4. EXERCISES
211
14.4
Exercises
212
(b) D5
(c) Z9
(d) Q8
14.4. EXERCISES
213
H
H
214
14.5
Programming Exercise
14.6
[1]
[2]
[3]
[4]
[5]
Laufer, H. B. Discrete Mathematics and Applied Modern Algebra. PWS-Kent, Boston, 1984.
[6]
[7]
Shapiro, L. W. Finite Groups Acting on Sets with Applications, Mathematics Magazine, MayJune 1973, 13647.
15
The Sylow Theorems
15.1
216
217
218
219
Historical Note
Peter Ludvig Mejdell Sylow was born in 1832 in Christiania,
Norway (now Oslo). After attending Christiania University, Sylow
taught high school. In 1862 he obtained a temporary appointment at Christiania University. Even though his appointment was
relatively brief, he influenced students such as Sophus Lie (1842
1899). Sylow had a chance at a permanent chair in 1869, but failed
to obtain the appointment. In 1872, he published a 10-page paper
presenting the theorems that now bear his name. Later Lie and Sylow collaborated on a new edition of Abels works. In 1898, a chair
at Christiania University was finally created for Sylow through the
efforts of his student and colleague Lie. Sylow died in 1918.
15.2
220
221
222
16 16
= 64,
4
15.3. EXERCISES
15.3
223
Exercises
1. What are the orders of all Sylow p-subgroups where G has order
18, 24, 54, 72, and 80?
2. Find all the Sylow 3-subgroups of S4 and show that they are all
conjugate.
3. Show that every group of order 45 has a normal subgroup of
order 9.
4. Let H be a Sylow p-subgroup of G. Prove that H is the only
Sylow p-subgroup of G contained in N (H).
5. Prove that no group of order 96 is simple.
6. Prove that no group of order 160 is simple.
7. If H is a normal subgroup of a finite group G and |H| = pk for
some prime p, show that H is contained in every Sylow p-subgroup
of G.
8. Let G be a group of order p2 q 2 , where p and q are distinct
primes such that q p2 1 and p q 2 1. Prove that G must be
abelian. Find a pair of primes for which this is true.
9. Show that a group of order 33 has only one Sylow 3-subgroup.
10. Let H be a subgroup of a group G. Prove or disprove that the
normalizer of H is normal in G.
11. Let G be a finite group divisible by a prime p. Prove that
if there is only one Sylow p-subgroup in G, it must be a normal
subgroup of G.
12. Let G be a group of order pr , p prime. Prove that G contains
a normal subgroup of order pr1 .
13. Suppose that G is a finite group of order pn k, where k < p.
Show that G must contain a normal subgroup.
14. Let H be a subgroup of a finite group G. Prove that gN (H)g 1 =
N (gHg 1 ) for any g G.
15. Prove that a group of order 108 must have a normal subgroup.
16. Classify all the groups of order 175 up to isomorphism.
17. Show that every group of order 255 is cyclic.
224
18. Let G have order pe11 penn and suppose that G has n Sylow
p-subgroups P1 , . . . , Pn where |Pi | = pei i . Prove that G is isomorphic to P1 Pn .
19. Let P be a normal Sylow p-subgroup of G. Prove that every
inner automorphism of G fixes P .
20. What is the smallest possible order of a group G such that G
is nonabelian and |G| is odd? Can you find such a group?
21. (The Frattini Lemma) If H is a normal subgroup of a finite
group G and P is a Sylow p-subgroup of H, for each g G show
that there is an h in H such that gP g 1 = hP h1 . Also, show
that if N is the normalizer of P , then G = HN .
22. Show that if the order of G is pn q, where p and q are primes
and p > q, then G contains a normal subgroup.
23. Prove that the number of distinct conjugates of a subgroup H
of a finite group G is [G : N (H)].
24. Prove that a Sylow 2-subgroup of S5 is isomorphic to D4 .
25. Another Proof of the Sylow Theorems.
(a) Suppose p is prime and p does not divide m. Show that
( k )
p m
p
.
pk
(b) Let S denote the set of all pk element subsets of G. Show that
p does not divide |S|.
(c) Define an action of G on S by left multiplication, aT = {at :
t T } for a G and T S. Prove that this is a group action.
(d) Prove p |OT | for some T S.
(e) Let {T1 , . . . , Tu } be an orbit such that p u and H = {g G :
gT1 = T1 }. Prove that H is a subgroup of G and show that
|G| = u|H|.
(f) Show that pk divides |H| and pk |H|.
(g) Show that |H| = |OT | pk ; conclude that therefore pk = |H|.
26. Let G be a group. Prove that G = aba1 b1 : a, b G is
a normal subgroup of G and G/G is abelian. Find an example to
show that {aba1 b1 : a, b G} is not necessarily a group.
15.4. A PROJECT
15.4
225
A Project
Number
?
?
?
?
?
?
?
?
?
?
?
5
?
?
1
Order
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Number
14
1
?
?
5
?
2
1
?
2
2
5
?
1
4
Order
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Number
1
51
1
?
1
14
1
?
2
14
1
?
1
4
?
Order
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
1. Find all simple groups G ( |G| 60). Do not use the Odd Order
Theorem unless you are prepared to prove it.
2. Find the number of distinct groups G, where the order of G is
n for n = 1, . . . , 60.
3. Find the actual groups (up to isomorphism) for each n.
15.5
[1]
Edwards, H. A Short History of the Fields Medal, Mathematical Intelligencer 1(1978), 12729.
[2]
Number
2
1
52
?
5
?
?
?
15
2
?
2
?
1
13
226
[3]
Gallian, J. A. The Search for Finite Simple Groups, Mathematics Magazine 49(1976), 16379.
[4]
Gorenstein, D. Classifying the Finite Simple Groups, Bulletin of the American Mathematical Society 14(1986), 198.
[5]
[6]
Gorenstein, D., Lyons, R., and Solomon, R. The Classification of Finite Simple Groups. American Mathematical Society, Providence RI, 1994.
16
Rings
Up to this point we have studied sets with a single binary operation satisfying certain axioms, but we are often more interested in
working with sets that have two binary operations. For example,
one of the most natural algebraic structures to study is the integers
with the operations of addition and multiplication. These operations are related to one another by the distributive property. If we
consider a set with two such related binary operations satisfying
certain axioms, we have an algebraic structure called a ring. In a
ring we add and multiply elements such as real numbers, complex
numbers, matrices, and functions.
16.1
Rings
228
Commutative
Rings
Rings with
Identity
Integral
Domains
Division
Rings
Fields
16.1. RINGS
229
(
i=
)
0 1
,
1 0
j=
(
)
0 i
,
i 0
(
k=
)
i 0
,
0 i
230
Though multiplication looks complicated, it is actually a straightforward computation if we remember that we just add and multiply
elements in H like polynomials and keep in mind the relationships
between the generators i, j, and k. The ring H is called the ring of
quaternions.
To show that the quaternions are a division ring, we must be
able to find an inverse for each nonzero element. Notice that
(a + bi + cj + dk)(a bi cj dk) = a2 + b2 + c2 + d2 .
This element can be zero only if a, b, c, and d are all zero. So if
a + bi + cj + dk = 0,
(
)
a bi cj dk
(a + bi + cj + dk)
= 1.
a2 + b2 + c2 + d2
Proposition 16.8. Let R be a ring with a, b R. Then
1. a0 = 0a = 0;
2. a(b) = (a)b = ab;
3. (a)(b) = ab.
Proof. To prove (1), observe that
a0 = a(0 + 0) = a0 + a0;
hence, a0 = 0. Similarly, 0a = 0. For (2), we have ab + a(b) =
a(b b) = a0 = 0; consequently, ab = a(b). Similarly, ab =
(a)b. Part (3) follows directly from (2) since (a)(b) = (a(b)) =
(ab) = ab.
Just as we have subgroups of groups, we have an analogous class
of substructures for rings. A subring S of a ring R is a subset S
of R such that S is also a ring under the inherited operations from
R.
Example 16.9. The ring nZ is a subring of Z. Notice that even
though the original ring may have an identity, we do not require
that its subring have an identity. We have the following chain of
subrings:
Z Q R C.
The following proposition gives us some easy criteria for determining whether or not a subset of a ring is indeed a subring. (We
will leave the proof of this proposition as an exercise.)
Proposition 16.10. Let R be a ring and S a subset of R. Then S
is a subring of R if and only if the following conditions are satisfied.
1. S = .
231
2. rs S for all r, s S.
3. r s S for all r, s S.
Example 16.11. Let R = M2 (R) be the ring of 2 2 matrices
with entries in R. If T is the set of upper triangular matrices in R;
i.e.,
{(
)
}
a b
T =
: a, b, c R ,
0 c
then T is a subring of R. If
(
)
a b
A=
0 c
and
( )
a b
B=
0 c
232
a
b
2.
+ 2
2
2b
a 2b2
233
16.3
(mod n)
(mod n) + b
= (a) + (b)
(mod n)
234
and
(ab) = ab
=a
(mod n)
(mod n) b (mod n)
= (a)(b).
The kernel of the homomorphism is nZ.
Example 16.21. Let C[a, b] be the ring of continuous real-valued
functions on an interval [a, b] as in Example 16.5. For a fixed
[a, b], we can define a ring homomorphism : C[a, b] R by
(f ) = f (). This is a ring homomorphism since
(f + g) = (f + g)() = f () + g() = (f ) + (g)
(f g) = (f g)() = f ()g() = (f ) (g).
Ring homomorphisms of the type are called evaluation homomorphisms.
In the next proposition we will examine some fundamental
properties of ring homomorphisms. The proof of the proposition is
left as an exercise.
Proposition 16.22. Let : R S be a ring homomorphism.
1. If R is a commutative ring, then (R) is a commutative ring.
2. (0) = 0.
3. Let 1R and 1S be the identities for R and S, respectively. If
is onto, then (1R ) = 1S .
4. If R is a field and (R) = {0}, then (R) is a field.
In group theory we found that normal subgroups play a special
role. These subgroups have nice characteristics that make them
more interesting to study than arbitrary subgroups. In ring theory
the objects corresponding to normal subgroups are a special class
of subrings called ideals. An ideal in a ring R is a subring I of R
such that if a is in I and r is in R, then both ar and ra are in I;
that is, rI I and Ir I for all r R.
Example 16.23. Every ring R has at least two ideals, {0} and R.
These ideals are called the trivial ideals.
Let R be a ring with identity and suppose that I is an ideal
in R such that 1 is in I. Since for any r R, r1 = r I by the
definition of an ideal, I = R.
Example 16.24. If a is any element in a commutative ring R with
identity, then the set
a = {ar : r R}
235
236
Proof. We already know that R/I is an abelian group under addition. Let r + I and s + I be in R/I. We must show that the
product (r +I)(s+I) = rs+I is independent of the choice of coset;
that is, if r r + I and s s + I, then r s must be in rs + I.
Since r r + I, there exists an element a in I such that r = r + a.
Similarly, there exists a b I such that s = s + b. Notice that
r s = (r + a)(s + b) = rs + as + rb + ab
and as + rb + ab I since I is an ideal; consequently, r s rs + I.
We will leave as an exercise the verification of the associative law
for multiplication and the distributive laws.
The ring R/I in Theorem 16.29 is called the factor or quotient
ring. Just as with group homomorphisms and normal subgroups,
there is a relationship between ring homomorphisms and ideals.
Theorem 16.30. Let I be an ideal of R. The map : R R/I
defined by (r) = r + I is a ring homomorphism of R onto R/I
with kernel I.
Proof. Certainly : R R/I is a surjective abelian group homomorphism. It remains to show that works correctly under
ring multiplication. Let r and s be in R. Then
(r)(s) = (r + I)(s + I) = rs + I = (rs),
which completes the proof of the theorem.
The map : R R/I is often called the natural or canonical
homomorphism. In ring theory we have isomorphism theorems
relating ideals and ring homomorphisms similar to the isomorphism
theorems for groups that relate normal subgroups and homomorphisms in Chapter 11. We will prove only the First Isomorphism
Theorem for rings in this chapter and leave the proofs of the other
two theorems as exercises. All of the proofs are similar to the proofs
of the isomorphism theorems for groups.
Theorem 16.31 (First Isomorphism Theorem). Let : R S be
a ring homomorphism. Then ker is an ideal of R. If : R
R/ ker is the canonical homomorphism, then there exists a unique
isomorphism : R/ ker (R) such that = .
237
Theorem 16.32 (Second Isomorphism Theorem). Let I be a subring of a ring R and J an ideal of R. Then I J is an ideal of I
and
I/I J
= (I + J)/J.
Theorem 16.33 (Third Isomorphism Theorem). Let R be a ring
and I and J be ideals of R where J I. Then
R/J
R/I
.
=
I/J
Theorem 16.34 (Correspondence Theorem). Let I be an ideal of
a ring R. Then S S/I is a one-to-one correspondence between
the set of subrings S containing I and the set of subrings of R/I.
Furthermore, the ideals of R containing I correspond to ideals of
R/I.
16.4
238
[3].
239
240
16.5
The Chinese Remainder Theorem is a result from elementary number theory about the solution of systems of simultaneous congruences. The Chinese mathematician Sun-ts wrote about the theorem in the first century A.D. This theorem has some interesting
consequences in the design of software for parallel processors.
Lemma 16.41. Let m and n be positive integers such that gcd(m, n) =
1. Then for a, b Z the system
x a (mod m)
x b (mod n)
has a solution. If x1 and x2 are two solutions of the system, then
x1 x2 (mod mn).
Proof. The equation x a (mod m) has a solution since a + km
satisfies the equation for all k Z. We must show that there exists
an integer k1 such that
a + k1 m b (mod n).
This is equivalent to showing that
k1 m (b a) (mod n)
241
(mod m)
ci b (mod n)
for i = 1, 2. Then
c2 c1
(mod m)
c2 c1
(mod n).
(mod 4)
x4
(mod 5).
(mod n1 )
x a2
..
.
(mod n2 )
x ak
(mod nk )
242
(mod n1 )
x a2
..
.
(mod n2 )
x ak+1
(mod nk+1 ).
(mod n1 nk )
x ak+1
(mod nk+1 )
(mod 4)
x4
(mod 5)
x1
(mod 9)
x5
(mod 7).
(mod 20)
x1
(mod 9)
x5
(mod 7).
243
(mod 95)
(mod 98)
2134 55
(mod 99)
and
1531 11 (mod 95)
1531 76 (mod 97)
1531 61 (mod 98)
1531 46 (mod 99).
Multiplying the corresponding equations, we obtain
2134 1531 44 11 9 (mod 95)
2134 1531 0 76 0
(mod 97)
244
16.6
Exercises
1. Which of the following sets are rings with respect to the usual
operations of addition and multiplication? If the set is a ring, is it
also a field?
(a) 7Z
(b) Z18
(c) Q( 2 ) = {a + b 2 : a, b Q}
(d) Q( 2, 3 ) = {a + b 2 + c 3 + d 6 : a, b, c, d Q}
(e) Z[ 3 ] = {a + b 3 : a, b Z}
(f) R = {a + b 3 3 : a, b Q}
(g) Z[i] = {a + bi : a, b Z and i2 = 1}
(h) Q( 3 3 ) = {a + b 3 3 + c 3 9 : a, b, c Q}
2. Let R be the ring of 2 2 matrices of the form
(
)
a b
,
0 0
where a, b R. Show that although R is a ring that has no identity,
we can find a subring S of R with an identity.
16.6. EXERCISES
245
Z10
Z12
Z7
M2 (Z), the 2 2 matrices with entries in Z
M2 (Z2 ), the 2 2 matrices with entries in Z2
Z18
Z25
M2 (R), the 2 2 matrices with entries in R
M2 (Z), the 2 2 matrices with entries in Z
Q
246
(a)
(c)
x2
(mod 4)
x 2 (mod 5)
x4
(mod 7)
x 6 (mod 11)
x7
(mod 9)
x5
(mod 11)
x3
(mod 5)
x 3 (mod 7)
x0
(mod 8)
x 0 (mod 8)
x1
(mod 11)
x 5 (mod 15)
x5
(mod 13)
(d)
(b)
16.6. EXERCISES
247
248
249
(mod I)
x s (mod J)
has a solution.
(b) In addition, prove that any two solutions of the system are
congruent modulo I J.
(c) Let I and J be ideals in a ring R such that I + J = R. Show
that there exists a ring isomorphism
R/(I J)
= R/I R/J.
16.7
Programming Exercise
1. Write a computer program implementing fast addition and multiplication using the Chinese Remainder Theorem and the method
outlined in the text.
16.8
[1]
[2]
Atiyah, M. F. and MacDonald, I. G. Introduction to Commutative Algebra. Westview Press, Boulder, CO, 1994.
[3]
[4]
Kaplansky, I. Commutative Rings. Revised edition. University of Chicago Press, Chicago, 1974.
[5]
Knuth, D. E. The Art of Computer Programming: SemiNumerical Algorithms, vol. 2. 3rd ed. Addison-Wesley Professional, Boston, 1997.
[6]
[7]
250
[8]
[9]
17
Polynomials
Most people are fairly familiar with polynomials by the time they
begin to study abstract algebra. When we examine polynomial
expressions such as
p(x) = x3 3x + 2
q(x) = 3x2 6x + 5,
we have a pretty good idea of what p(x) + q(x) and p(x)q(x) mean.
We just add and multiply polynomials as functions; that is,
(p + q)(x) = p(x) + q(x)
= (x3 3x + 2) + (3x2 6x + 5)
= x3 + 3x2 9x + 7
and
(pq)(x) = p(x)q(x)
= (x3 3x + 2)(3x2 6x + 5)
= 3x5 6x4 4x3 + 24x2 27x + 10.
It is probably no surprise that polynomials form a ring. In this
chapter we shall emphasize the algebraic structure of polynomials by studying polynomial rings. We can prove many results for
polynomial rings that are similar to the theorems we proved for the
integers. Analogs of prime numbers, the division algorithm, and
the Euclidean algorithm exist for polynomials.
17.1
Polynomial Rings
ai xi = a0 + a1 x + a2 x2 + + an xn ,
i=0
251
252
k=0
for each i. Notice that in each case some of the coefficients may be
zero.
Example 17.1. Suppose that
p(x) = 3 + 0x + 0x2 + 2x3 + 0x4
and
q(x) = 2 + 0x x2 + 0x3 + 4x4
are polynomials in Z[x]. If the coefficient of some term in a polynomial is zero, then we usually just omit that term. In this case
we would write p(x) = 3 + 2x3 and q(x) = 2 x2 + 4x4 . The sum
of these two polynomials is
p(x) + q(x) = 5 x2 + 2x3 + 4x4 .
253
The product,
p(x) = 3 + 3x3
and
be polynomials in Z12 [x]. The sum of p(x) and q(x) is 7+4x2 +3x3 +
4x4 . The product of the two polynomials is the zero polynomial.
This example tells us that we can not expect R[x] to be an integral
domain if R is not an integral domain.
p(x) =
q(x) =
r(x) =
i=0
n
i=0
p
i=0
ai xi ,
bi xi ,
ci xi .
254
Then
[(
[p(x)q(x)]r(x) =
m+n+p
m+n+p
(
i
aj bij x
)
ci x
i=0
p
)
i
ci x
i=0
( j
)
i
ak bjk cij xi
k=0
aj bk cl xi
)
( ij
i
aj
bk cijk xi
j=0
k=0
) n+p i
m
ai xi
bj cij xi
i=0
bi x
j+k+l=i
m+n+p
i=0
)] (
i=0
i
j=0
i=0
j=0
i=0
ai x
i=0
m+n
i=0
)(
i
i=0
) [(
ai xi
i=0
j=0
)(
bi xi
i=0
)]
ci xi
i=0
= p(x)[q(x)r(x)]
The commutativity and distribution properties of polynomial multiplication are proved in a similar manner. We shall leave the proofs
of these properties as an exercise.
Proposition 17.4. Let p(x) and q(x) be polynomials in R[x],
where R is an integral domain. Then deg p(x)+deg q(x) = deg(p(x)q(x)).
Furthermore, R[x] is an integral domain.
Proof. Suppose that we have two nonzero polynomials
p(x) = am xm + + a1 x + a0
and
q(x) = bn xn + + b1 x + b0
with am = 0 and bn = 0. The degrees of p(x) and q(x) are m
and n, respectively. The leading term of p(x)q(x) is am bn xm+n ,
which cannot be zero since R is an integral domain; hence, the
degree of p(x)q(x) is m + n, and p(x)q(x) = 0. Since p(x) = 0 and
q(x) = 0 imply that p(x)q(x) = 0, we know that R[x] must also be
an integral domain.
We also want to consider polynomials in two or more variables,
such as x2 3xy + 2y 3 . Let R be a ring and suppose that we are
255
i
Proof. Let p(x) = ni=0 ai xi and q(x) = m
i=0 bi x . It is easy to
show that (p(x) + q(x)) = (p(x)) + (q(x)). To show that
multiplication is preserved under the map , observe that
(p(x)) (q(x)) = p()q()
( n
)( m
)
i
i
ai
bi
=
i=0
( i
m+n
i=0
i=0
ak bik
k=0
= (p(x)q(x)).
17.2
Recall that the division algorithm for integers (Theorem 2.9) says
that if a and b are integers with b > 0, then there exist unique
integers q and r such that a = bq + r, where 0 r < b. The
algorithm by which q and r are found is just long division. A
similar theorem exists for polynomials. The division algorithm for
polynomials has several important consequences. Since its proof is
very similar to the corresponding proof for integers, it is worthwhile
to review Theorem 2.9 at this point.
Theorem 17.6 (Division Algorithm). Let f (x) and g(x) be polynomials in F [x], where F is a field and g(x) is a nonzero polynomial.
Then there exist unique polynomials q(x), r(x) F [x] such that
f (x) = g(x)q(x) + r(x),
256
where either deg r(x) < deg g(x) or r(x) is the zero polynomial.
Proof. We will first consider the existence of q(x) and r(x). If
f (x) is the zero polynomial, then
0 = 0 g(x) + 0;
hence, both q and r must also be the zero polynomial. Now suppose
that f (x) is not the zero polynomial and that deg f (x) = n and
deg g(x) = m. If m > n, then we can let q(x) = 0 and r(x) = f (x).
Hence, we may assume that m n and proceed by induction on
n. If
f (x) = an xn + an1 xn1 + + a1 x + a0
g(x) = bm xm + bm1 xm1 + + b1 x + b0
the polynomial
f (x) = f (x)
an nm
x
g(x)
bm
257
Example 17.7. The division algorithm merely formalizes long division of polynomials, a task we have been familiar with since high
school. For example, suppose that we divide x3 x2 + 2x 3 by
x 2.
x2
x3
x3
x
x2
2x2
x2
x2
+
+
4
2x
2x
2x
4x
4x
3
8
5
Hence, x3 x2 + 2x 3 = (x 2)(x2 + x + 4) + 5.
Let p(x) be a polynomial in F [x] and F . We say that
is a zero or root of p(x) if p(x) is in the kernel of the evaluation
homomorphism . All we are really saying here is that is a zero
of p(x) if p() = 0.
Corollary 17.8. Let F be a field. An element F is a zero of
p(x) F [x] if and only if x is a factor of p(x) in F [x].
Proof. Suppose that F and p() = 0. By the division algorithm, there exist polynomials q(x) and r(x) such that
p(x) = (x )q(x) + r(x)
and the degree of r(x) must be less than the degree of x . Since
the degree of r(x) is less than 1, r(x) = a for a F ; therefore,
p(x) = (x )q(x) + a.
But
0 = p() = 0 q() + a = a;
consequently, p(x) = (x )q(x), and x is a factor of p(x).
Conversely, suppose that x is a factor of p(x); say p(x) =
(x )q(x). Then p() = 0 q() = 0.
Corollary 17.9. Let F be a field. A nonzero polynomial p(x) of
degree n in F [x] can have at most n distinct zeros in F .
Proof. We will use induction on the degree of p(x). If deg p(x) =
0, then p(x) is a constant polynomial and has no zeros. Let deg p(x) =
1. Then p(x) = ax + b for some a and b in F . If 1 and 2 are
zeros of p(x), then a1 + b = a2 + b or 1 = 2 .
258
Now assume that deg p(x) > 1. If p(x) does not have a zero in
F , then we are done. On the other hand, if is a zero of p(x), then
p(x) = (x )q(x) for some q(x) F [x] by Corollary 17.8. The
degree of q(x) is n1 by Proposition 17.4. Let be some other zero
of p(x) that is distinct from . Then p() = ( )q() = 0. Since
= and F is a field, q() = 0. By our induction hypothesis,
p(x) can have at most n 1 zeros in F that are distinct from .
Therefore, p(x) has at most n distinct zeros in F .
Let F be a field. A monic polynomial d(x) is a greatest common divisor of polynomials p(x), q(x) F [x] if d(x) evenly divides both p(x) and q(x); and, if for any other polynomial d (x) dividing both p(x) and q(x), d (x) | d(x). We write d(x) = gcd(p(x), q(x)).
Two polynomials p(x) and q(x) are relatively prime if gcd(p(x), q(x)) =
1.
Proposition 17.10. Let F be a field and suppose that d(x) is a
greatest common divisor of two polynomials p(x) and q(x) in F [x].
Then there exist polynomials r(x) and s(x) such that
d(x) = r(x)p(x) + s(x)q(x).
Furthermore, the greatest common divisor of two polynomials is
unique.
Proof. Let d(x) be the monic polynomial of smallest degree in
the set
S = {f (x)p(x) + g(x)q(x) : f (x), g(x) F [x]}.
We can write d(x) = r(x)p(x) + s(x)q(x) for two polynomials r(x)
and s(x) in F [x]. We need to show that d(x) divides both p(x)
and q(x). We shall first show that d(x) divides p(x). By the
division algorithm, there exist polynomials a(x) and b(x) such that
p(x) = a(x)d(x) + b(x), where b(x) is either the zero polynomial or
deg b(x) < deg d(x). Therefore,
b(x) = p(x) a(x)d(x)
= p(x) a(x)(r(x)p(x) + s(x)q(x))
= p(x) a(x)r(x)p(x) a(x)s(x)q(x)
= p(x)(1 a(x)r(x)) + q(x)(a(x)s(x))
is a linear combination of p(x) and q(x) and therefore must be
in S. However, b(x) must be the zero polynomial since d(x) was
chosen to be of smallest degree; consequently, d(x) divides p(x). A
symmetric argument shows that d(x) must also divide q(x); hence,
d(x) is a common divisor of p(x) and q(x).
To show that d(x) is a greatest common divisor of p(x) and
q(x), suppose that d (x) is another common divisor of p(x) and
259
17.3
Irreducible Polynomials
260
b0 b1
bn
+ x + + xn ,
c0 c1
cn
1
(d0 + d1 x + + dn xn ),
c0 cn
d
(a0 + a1 x + + an xn ),
c0 cn
(x) =
where the ai s are relatively prime and the bi s are relatively prime.
Consequently,
p(x) = (x)(x) =
c1 c2
c
1 (x)1 (x) = 1 (x)1 (x),
d1 d2
d
261
262
Ideals in F [x]
Let F be a field. Recall that a principal ideal in F [x] is an ideal
p(x) generated by some polynomial p(x); that is,
p(x) = {p(x)q(x) : q(x) F [x]}.
263
264
Sage Polynomial rings are very important for computational approaches to algebra, and so Sage makes it very easy to compute
with polynomials, over rings, or over fields. And it is trivial to
check if a polynomial is irreducible.
Historical Note
Throughout history, the solution of polynomial equations has
been a challenging problem. The Babylonians knew how to solve
the equation ax2 +bx+c = 0. Omar Khayyam (10481131) devised
methods of solving cubic equations through the use of geometric
constructions and conic sections. The algebraic solution of the
general cubic equation ax3 + bx2 + cx + d = 0 was not discovered
until the sixteenth century. An Italian mathematician, Luca Pacioli
(ca. 14451509), wrote in Summa de Arithmetica that the solution
of the cubic was impossible. This was taken as a challenge by the
rest of the mathematical community.
Scipione del Ferro (14651526), of the University of Bologna,
solved the depressed cubic,
ax3 + cx + d = 0.
He kept his solution an absolute secret. This may seem surprising today, when mathematicians are usually very eager to publish
their results, but in the days of the Italian Renaissance secrecy was
customary. Academic appointments were not easy to secure and
depended on the ability to prevail in public contests. Such challenges could be issued at any time. Consequently, any major new
discovery was a valuable weapon in such a contest. If an opponent
presented a list of problems to be solved, del Ferro could in turn
present a list of depressed cubics. He kept the secret of his discovery throughout his life, passing it on only on his deathbed to his
student Antonio Fior (ca. 1506?).
Although Fior was not the equal of his teacher, he immediately
issued a challenge to Niccolo Fontana (14991557). Fontana was
known as Tartaglia (the Stammerer). As a youth he had suffered
a blow from the sword of a French soldier during an attack on his
village. He survived the savage wound, but his speech was permanently impaired. Tartaglia sent Fior a list of 30 various mathematical problems; Fior countered by sending Tartaglia a list of 30 depressed cubics. Tartaglia would either solve all 30 of the problems
or absolutely fail. After much effort Tartaglia finally succeeded
in solving the depressed cubic and defeated Fior, who faded into
obscurity.
At this point another mathematician, Gerolamo Cardano (1501
1576), entered the story. Cardano wrote to Tartaglia, begging him
for the solution to the depressed cubic. Tartaglia refused several
of his requests, then finally revealed the solution to Cardano after
the latter swore an oath not to publish the secret or to pass it on
17.4. EXERCISES
265
17.4
Exercises
266
(b) p(x) = x3 +x2 x+1 and q(x) = x3 +x1, where p(x), q(x)
Z2 [x]
(c) p(x) = x3 + x2 4x + 4 and q(x) = x3 + 3x 2, where
p(x), q(x) Z5 [x]
(d) p(x) = x3 2x + 4 and q(x) = 4x3 + x + 3, where p(x), q(x)
Q[x]
5. Find all of the zeros for each of the following polynomials.
(a) 5x3 + 4x2 x + 9 in Z12
(d) x3 + x + 1 in Z2
(b) x4 5x3 + 3x 2
17.4. EXERCISES
267
268
17.5
b2 4ac
.
2a
The discriminant of the quadratic equation = b2 4ac determines the nature of the solutions of the equation. If > 0, the
equation has two distinct real solutions. If = 0, the equation
has a single repeated real root. If < 0, there are two distinct
imaginary solutions.
x=
1 + i 3
=
2
1
i 3
2 =
2
3 = 1.
4. Make the substitution
y=z
p
3z
3
deducing that AB = p/3.
6. Prove that the possible solutions for z in (4) are given by
3
3
3
3
3
3
A, A, 2 A,
B, B, 2 B
and use this result to show that the three possible solutions for y
are
3
2
p
p3
q
q
q
q2
i 3
2i 3
+
+
+
+ ,
2
27
4
2
27
4
where i = 0, 1, 2.
7. The discriminant of the cubic equation is
=
p3
q2
+ .
27
4
Show that y 3 + py + q = 0
(a) has three real roots, at least two of which are equal, if = 0.
(b) has one real root and two conjugate imaginary roots if > 0.
(c) has three distinct real roots if < 0.
8. Solve the following cubic equations.
(a) x3 4x2 + 11x + 30 = 0
(b) x3 3x + 5 = 0
(c) x3 3x + 2 = 0
(d) x3 + x + 3 = 0
9. Show that the general quartic equation
x4 + ax3 + bx2 + cx + d = 0
can be reduced to
y 4 + py 2 + qy + r = 0
by using the substitution x = y a/4.
10. Show that
)
(
)
(
1 2
1 2
z r .
y 2 + z = (z p)y 2 qy +
2
4
270
11. Show that the right-hand side of Exercise 17.5.10 can be put
in the form (my + k)2 if and only if
(
)
1 2
2
q 4(z p)
z r = 0.
4
12. From Exercise 17.5.11 obtain the resolvent cubic equation
z 3 pz 2 4rz + (4pr q 2 ) = 0.
Solving the resolvent cubic equation, put the equation found in
Exercise 17.5.10 in the form
(
)
1 2
2
y + z = (my + k)2
2
to obtain the solution of the quartic equation.
13. Use this method to solve the following quartic equations.
(a) x4 x2 3x + 2 = 0
(b) x4 + x3 7x2 x + 6 = 0
(c) x4 2x2 + 4x 3 = 0
(d) x4 4x3 + 3x2 5x + 2 = 0
18
Integral Domains
18.1
Fields of Fractions
272
c
ad + bc
=
;
d
bd
c
ac
= .
d
bd
It seems reasonable to define the operations of addition and multiplication on FD in a similar manner. If we denote the equivalence
class of (a, b) S by [a, b], then we are led to define the operations
of addition and multiplication on FD by
[a, b] + [c, d] = [ad + bc, bd]
and
[a, b] [c, d] = [ac, bd],
respectively. The next lemma demonstrates that these operations
are independent of the choice of representatives from each equivalence class.
Lemma 18.2. The operations of addition and multiplication on
FD are well-defined.
273
274
275
18.2
276
4 = 2 2 = (1 3 i)(1 + 3 i).
We must
show that each of these factors is an irreducible element
in
Z[ 3 i]. If 2 is not irreducible, then 2 = zw for elements z, w in
Z[ 3 i] where (z)
= (w) = 2. However, there does not exist an
element in z in Z[ 3 i] such that (z) = 2 because the equation a2 +
3b2 = 2 has no integer solutions. Therefore,2 must be irreducible.
277
278
279
Euclidean Domains
We have repeatedly used the division algorithm when proving results about either Z or F [x], where F is a field. We should now
ask when a division algorithm is available for an integral domain.
Let D be an integral domain such that for each a D there is
a nonnegative integer (a) satisfying the following conditions.
1. If a and b are nonzero elements in D, then (a) (ab).
2. Let a, b D and suppose that b = 0. Then there exist
elements q, r D such that a = bq + r and either r = 0 or
(r) < (b).
Then D is called a Euclidean domain and is called a Euclidean valuation.
Example 18.18. Absolute value on Z is a Euclidean valuation.
Example 18.19. Let F be a field. Then the degree of a polynomial
in F [x] is a Euclidean valuation.
Example 18.20. Recall that the Gaussian integers in Example 16.12
of Chapter 16 are defined by
Z[i] = {a + bi : a, b Z}.
We usually measure the
size of a complex number
a + bi by its
2
2
2
2
absolute value, |a + bi| = a + b ; however, a + b may not be
an integer. For our valuation we will let (a + bi) = a2 + b2 to
ensure that we have an integer.
We claim that (a + bi) = a2 + b2 is a Euclidean valuation on
Z[i]. Let z, w Z[i]. Then (zw) = |zw|2 = |z|2 |w|2 = (z)(w).
Since (z) 1 for every nonzero z Z[i], (z) (z)(w).
Next, we must show that for any z = a + bi and w = c + di
in Z[i] with w = 0, there exist elements q and r in Z[i] such that
z = qw + r with either r = 0 or (r) < (w). We can view z and
280
zw1 = (a + bi)
in Q(i). In the last steps we are writing the real and imaginary
parts as an integer plus a proper fraction. That is, we take the
closest integer mi such that the fractional part satisfies |ni /(a2 +
b2 )| 1/2. For example, we write
9
=1+
8
15
=2
8
1
8
1
.
8
281
Factorization in D[x]
One of the most important polynomial rings is Z[x]. One of the
first questions that come to mind about Z[x] is whether or not
it is a UFD. We will prove a more general statement here. Our
first task is to obtain a more general version of Gausss Lemma
(Theorem 17.14).
Let D be a unique factorization domain and suppose that
p(x) = an xn + + a1 x + a0
in D[x]. Then the content of p(x) is the greatest common divisor
of a0 , . . . , an . We say that p(x) is primitive if gcd(a0 , . . . , an ) = 1.
Example 18.23. In Z[x] the polynomial p(x) = 5x4 3x3 + x 4
is a primitive polynomial since the greatest common divisor of the
coefficients is 1; however, the polynomial q(x) = 4x2 6x + 8 is
not primitive since the content of q(x) is 2.
Theorem 18.24 (Gausss Lemma). Let D be a UFD and let f (x)
and g(x) be primitive polynomials in D[x]. Then f (x)g(x) is primitive.
n
m
i
i
Proof. Let f (x) =
i=0 bi x . Suppose
i=0 ai x and g(x) =
that p is a prime dividing the coefficients of f (x)g(x). Let r be the
smallest integer such that p |ar and s be the smallest integer such
that p |bs . The coefficient of xr+s in f (x)g(x) is
cr+s = a0 br+s + a1 br+s1 + + ar+s1 b1 + ar+s b0 .
Since p divides a0 , . . . , ar1 and b0 , . . . , bs1 , p divides every term
of cr+s except for the term ar bs . However, since p | cr+s , either p
divides ar or p divides bs . But this is impossible.
Lemma 18.25. Let D be a UFD, and let p(x) and q(x) be in D[x].
Then the content of p(x)q(x) is equal to the product of the contents
of p(x) and q(x).
Proof. Let p(x) = cp1 (x) and q(x) = dq1 (x), where c and d are
the contents of p(x) and q(x), respectively. Then p1 (x) and q1 (x)
are primitive. We can now write p(x)q(x) = cdp1 (x)q1 (x). Since
p1 (x)q1 (x) is primitive, the content of p(x)q(x) must be cd.
Lemma 18.26. Let D be a UFD and F its field of fractions.
Suppose that p(x) D[x] and p(x) = f (x)g(x), where f (x) and g(x)
are in F [x]. Then p(x) = f1 (x)g1 (x), where f1 (x) and g1 (x) are in
D[x]. Furthermore, deg f (x) = deg f1 (x) and deg g(x) = deg g1 (x).
282
283
284
18.3
Exercises
2 = 1, show that z
1. Let z = a + b 3 i be in Z[ 3 i]. If a2 + 3b
must be a unit. Show that the only units of Z[ 3 i] are 1 and 1.
2. The Gaussian integers, Z[i], are a UFD. Factor each of the following elements in Z[i] into a product of irreducibles.
(a) 5
(c) 6 + 8i
(b) 1 + 3i
(d) 2
18.3. EXERCISES
285
286
287
(b) Let a/s denote the equivalence class of (a, s) R S and let
S 1 R be the set of all equivalence classes with respect to .
Define the operations of addition and multiplication on S 1 R
by
a b
at + bs
+ =
s
t
st
ab
ab
= ,
st
st
respectively. Prove that these operations are well-defined on
S 1 R and that S 1 R is a ring with identity under these operations. The ring S 1 R is called the ring of quotients of
R with respect to S.
(c) Show that the map : R S 1 R defined by (a) = a/1 is
a ring homomorphism.
(d) If R has no zero divisors and 0
/ S, show that is one-to-one.
(e) Prove that P is a prime ideal of R if and only if S = R \ P is
a multiplicative subset of R.
(f) If P is a prime ideal of R and S = R \ P , show that the ring
of quotients S 1 R has a unique maximal ideal. Any ring that
has a unique maximal ideal is called a local ring.
Atiyah, M. F. and MacDonald, I. G. Introduction to Commutative Algebra. Westview Press, Boulder, CO, 1994.
[2]
19
Lattices and Boolean
Algebras
19.1
Lattices
19.1. LATTICES
289
Example 19.2. Let X be any set. We will define the power set
of X to be the set of all subsets of X. We denote the power set of
X by P(X). For example, let X = {a, b, c}. Then P(X) is the set
of all subsets of the set {a, b, c}:
{a}
{b}
{c}
{a, b}
{a, c}
{b, c}
{a, b, c}.
{a, c}
{b, c}
{a}
{b}
{c}
12
3
1
19.1. LATTICES
291
19.2
Boolean Algebras
293
295
297
19.3
The usefulness of Boolean algebras has become increasingly apparent over the past several decades with the development of the
modern computer. The circuit design of computer chips can be expressed in terms of Boolean algebras. In this section we will develop
the Boolean algebra of electrical circuits and switches; however,
these results can easily be generalized to the design of integrated
computer circuitry.
A switch is a device, located at some point in an electrical
circuit, that controls the flow of current through the circuit. Each
switch has two possible states: it can be open, and not allow the
passage of current through the circuit, or a it can be closed, and
allow the passage of current. These states are mutually exclusive.
We require that every switch be in one state or the othera switch
cannot be open and closed at the same time. Also, if one switch
is always in the same state as another, we will denote both by the
same letter; that is, two switches that are both labeled with the
same letter a will always be open at the same time and closed at
the same time.
Given two switches, we can construct two fundamental types
of circuits. Two switches a and b are in series if they make up a
circuit of the type that is illustrated in Figure 19.25. Current can
pass between the terminals A and B in a series circuit only if both
of the switches a and b are closed. We will denote this combination
of switches by a b. Two switches a and b are in parallel if they
form a circuit of the type that appears in Figure 19.26. In the case
of a parallel circuit, current can pass between A and B if either
one of the switches is closed. We denote a parallel combination of
circuits a and b by a b.
A
Figure 19.25: a b
a
A
B
b
Figure 19.26: a b
299
Figure 19.27: a (b c) = (a b) (a c)
a
a
a
a
Figure 19.32: (a b) (a b ) (a b)
Sage Sage has a full suite of functionality for both posets and
lattices, all as part of its excellent support for combinatorics. There
is little in this chapter that cannot be investigated with Sage.
Historical Note
George Boole (18151864) was the first person to study lattices.
In 1847, he published The Investigation of the Laws of Thought, a
book in which he used lattices to formalize logic and the calculus
of propositions. Boole believed that mathematics was the study of
form rather than of content; that is, he was not so much concerned
with what he was calculating as with how he was calculating it.
Booles work was carried on by his friend Augustus De Morgan
(18061871). De Morgan observed that the principle of duality
often held in set theory, as is illustrated by De Morgans laws for
set theory. He believed, as did Boole, that mathematics was the
study of symbols and abstract operations.
Set theory and logic were further advanced by such mathematicians as Alfred North Whitehead (18611947), Bertrand Russell
(18721970), and David Hilbert (18621943). In Principia Mathematica, Whitehead and Russell attempted to show the connection
between mathematics and logic by the deduction of the natural
number system from the rules of formal logic. If the natural numbers could be determined from logic itself, then so could much of
the rest of existing mathematics. Hilbert attempted to build up
mathematics by using symbolic logic in a way that would prove the
consistency of mathematics. His approach was dealt a mortal blow
by Kurt Gdel (19061978), who proved that there will always be
undecidable problems in any sufficiently rich axiomatic system;
19.4. EXERCISES
301
19.4
Exercises
(c) a (a b)
(b) (a b) (a b)
(d) (c a b) c (a b)
7. Draw a circuit that will be closed exactly when only one of three
switches a, b, and c are closed.
8. Prove or disprove that the two circuits shown are equivalent.
a
a
a
b
b
a
303
(d) I = O and O = I.
(e) (a b) = a b and (a b) = a b (De Morgans laws).
16. By drawing the appropriate diagrams, complete the proof of
Theorem 19.14 to show that the switching functions form a Boolean
algebra.
17. Let B be a Boolean algebra. Define binary operations + and
on B by
a + b = (a b ) (a b)
a b = a b.
Prove that B is a commutative ring under these operations satisfying a2 = a for all a B.
18. Let X be a poset such that for every a and b in X, either a b
or b a. Then X is said to be a totally ordered set.
(a) Is a | b a total order on N?
(b) Prove that N, Z, Q, and R are totally ordered sets under the
usual ordering .
19. Let X and Y be posets. A map : X Y is orderpreserving if a b implies that (a) (b). Let L and M
be lattices. A map : L M is a lattice homomorphism if
(a b) = (a) (b) and (a b) = (a) (b). Show that
every lattice homomorphism is order-preserving, but that it is not
the case that every order-preserving homomorphism is a lattice
homomorphism.
20. Let B be a Boolean algebra. Prove that a = b if and only if
(a b ) (a b) = O for a, b B.
21. Let B be a Boolean algebra. Prove that a = 0 if and only if
(a b ) (a b) = b for all b B.
22. Let L and M be lattices. Define an order relation on L M
by (a, b) (c, d) if a c and b d. Show that L M is a lattice
under this partial order.
19.5
Programming Exercises
y
0
1
0
1
x
1
1
0
0
xy
0
1
1
1
xy
0
0
0
1
19.6
[1]
[2]
[3]
Hohn, F. Some Mathematical Aspects of Switching, American Mathematical Monthly 62(1955), 7590.
[4]
[5]
[6]
2nd ed.
20
Vector Spaces
20.1
306
20.2. SUBSPACES
20.2
307
Subspaces
i vi = 1 v1 + 2 v2 + + n vn
i=1
308
Then
u + v = (1 + 1 )v1 + (2 + 2 )v2 + + (n + n )vn
is a linear combination of the vi s. For F ,
u = (1 )v1 + (2 )v2 + + (n )vn
is in the span of S.
20.3
Linear Independence
309
1
k1
k+1
n
v1
vk1
vk+1
vn .
k
k
k
k
Example
20.13.
Let Q( 2 ) = {a + b 2 : a, b
Q}. The sets
310
20.4 Exercises
1. If F is a field, show that F [x] is a vector space over F , where
the vectors in F [x] are polynomials. Vector addition is polynomial
addition, and scalar multiplication is defined by p(x) for F .
20.4. EXERCISES
311
312
313
(c) Let U be a subspace of dimension k of a vector space W of dimension n. Prove that there exists a subspace V of dimension
n k such that W = U V . Is the subspace V unique?
(d) If U and V are arbitrary subspaces of a vector space W , show
that
dim(U + V ) = dim U + dim V dim(U V ).
18. (Dual Spaces) Let V and W be finite dimensional vector
spaces over a field F .
(a) Show that the set of all linear transformations from V into
W , denoted by Hom(V, W ), is a vector space over F , where
we define vector addition as follows:
[2]
Bretscher, O. Linear Algebra with Applications. 4th ed. Pearson, Upper Saddle River, NJ, 2009.
[3]
314
[4]
Hoffman, K. and Kunze, R. Linear Algebra. 2nd ed. PrenticeHall, Englewood Cliffs, NJ, 1971.
[5]
[6]
Leon, S. J. Linear Algebra with Applications. 8th ed. Pearson, Upper Saddle River, NJ, 2010.
21
Fields
Q( 2) = {a + b 2 : a, b Q}.
We wish to be able to compute and study such fields for arbitrary
polynomials over a field F .
21.1
Extension Fields
F = Q( 2 ) = {a + b 2 : a, b Q}
and let
E=
Q( 2 + 3 ) be the smallest field containing both Q
and 2 + 3. Both E and F are extension fields of the rational
numbers. We claim that E is an extension field of F . To see
315
316
this, we
need
only
show
that
2
is
in
E.
Since
2
+
3 is in
E, 1/( 2 + 3 )=
3 2
must
also be in E. Taking
linear
+
0
1
1+
0
0
1
1+
1
1
0
1+
1+
0
1
1+ 1+
1
0
Table 21.3: Addition Table for Z2 ()
0
1
1+
317
0
1
1+
0
0
0
0
0
1
1+
0
1+
1
0 1+
1
318
then
p() = a0 + a1 (x + p(x)) + + an (x + p(x))n
= a0 + (a1 x + p(x)) + + (an xn + p(x))
= a0 + a1 x + + an xn + p(x)
= 0 + p(x).
Therefore, we have found an element E = F [x]/p(x) such
that is a zero of p(x).
Example 21.6. Let p(x) = x5 + x4 + 1 Z2 [x]. Then p(x) has
irreducible factors x2 + x + 1 and x3 + x + 1. For a field extension
E of Z2 such that p(x) has a root in E, we can let E be either
Z2 [x]/x2 + x + 1 or Z2 [x]/x3 + x + 1. We will leave it as an
exercise to show that Z2 [x]/x3 + x + 1 is a field with 23 = 8
elements.
Algebraic Elements
An element in an extension field E over F is algebraic over F
if f () = 0 for some nonzero polynomial f (x) F [x]. An element
in E that is not algebraic over F is transcendental over F . An
extension field E of a field F is an algebraic extension of F if
every element in E is algebraic over F . If E is a field extension of
F and 1 , . . . , n are contained in E, we denote the smallest field
containing F and 1 , . . . , n by F (1 , . . . , n ). If E = F () for
some E, then E is a simple extension of F .
Example 21.7. Both 2 and i are algebraic over Q since they are
zeros of the polynomials x2 2 and x2 + 1, respectively. Clearly
and e are algebraic over the real numbers; however, it is a nontrivial
fact that they are transcendental over Q. Numbers in R that are
algebraic over Q are in fact quite rare. Almost all real numbers are
transcendental over Q.1 (In many cases we do not know whether
or not a particular number is transcendental; for example, it is still
not known whether + e is transcendental or algebraic.)
A complex number that is algebraic over Q is an algebraic
number. A transcendental number is an element of C that is
transcendental over Q.
Example
We will show that 2 + 3 is algebraic over Q.
21.8.
319
320
321
322
aij i j =
aij (i j ).
u=
j=1
i=1
i,j
cij (i j ) = 0
i,j
for cij F . We need to prove that all of the cij s are zero. We can
rewrite u as
( n
)
m
cij i j = 0,
j=1
i=1
cij i = 0
i=1
323
Example
21.20. Let us determine an extension field of Q containing 3 + 5. It is easy to determine that the minimal polynomial
of 3 + 5 is x4 16x2 + 4. It follows that
[Q( 3 + 5 ) : Q] = 4.
We know that {1,
3 ) over Q. Hence,
3+ 5
3 } is a basis for Q(
be inQ( 3) either.
cannot be in Q( 3 ). It follows that 5 cannot
Therefore,
{1,
5
}
is
a
basis
for
Q(
3,
5
)
=
(Q( 3 ))(
5) over
{1,
3,
5,
3
5
=
15
}
is
a
basis
for
Q(
3, 5 ) =
Q(3 ) and
3
Example
21.21.
Let
us
compute
a
basis
for
Q(
5,
5 i), where
3
5 is the positivesquare root
of
5
and
5
is
the
real
cube
root of
5. We know that 5 i
/ Q( 3 5 ), so
3
3
[Q( 5, 5 i) : Q( 5 )] = 2.
3
It iseasy to determine that {1, 5i
}
is
a
basis
for
Q(
5,
5 i)
over
3
3
2 } is a basis for Q( 3 5 )
Q( 3 5 ). We also know that {1,
5,
(
5
)
over Q. Hence, a basis for Q( 3 5, 5 i) over Q is
3
3
6
6
6
6
{1, 5 i, 5, ( 5 )2 , ( 5 )5 i, ( 5 )7 i = 5 5 i or 5 i}.
Notice that 6 5 i is a zero of x6 + 5. We can show that this polynomial is irreducible over Q using Eisensteins Criterion, where we
let p = 5. Consequently,
6
3
Q Q( 5 i) Q( 5, 5 i).
324
Theorem 21.22. Let E be a field extension of F . Then the following statements are equivalent.
1. E is a finite extension of F .
2. There exists a finite number of algebraic elements 1 , . . . , n
E such that E = F (1 , . . . , n ).
3. There exists a sequence of fields
E = F (1 , . . . , n ) F (1 , . . . , n1 ) F (1 ) F,
where each field F (1 , . . . , i ) is algebraic over F (1 , . . . , i1 ).
Proof. (1) (2). Let E be a finite algebraic extension of F .
Then E is a finite dimensional vector space over F and there
exists a basis consisting of elements 1 , . . . , n in E such that
E = F (1 , . . . , n ). Each i is algebraic over F by Theorem 21.15.
(2) (3). Suppose that E = F (1 , . . . , n ), where every i is
algebraic over F . Then
E = F (1 , . . . , n ) F (1 , . . . , n1 ) F (1 ) F,
where each field F (1 , . . . , i ) is algebraic over F (1 , . . . , i1 ).
(3) (1). Let
E = F (1 , . . . , n ) F (1 , . . . , n1 ) F (1 ) F,
where each field F (1 , . . . , i ) is algebraic over F (1 , . . . , i1 ).
Since
F (1 , . . . , i ) = F (1 , . . . , i1 )(i )
is simple extension and i is algebraic over F (1 , . . . , i1 ), it follows that
[F (1 , . . . , i ) : F (1 , . . . , i1 )]
is finite for each i. Therefore, [E : F ] is finite.
Algebraic Closure
Given a field F , the question arises as to whether or not we can
find a field E such that every polynomial p(x) has a root in E.
This leads us to the following theorem.
Theorem 21.23. Let E be an extension field of F . The set of
elements in E that are algebraic over F form a field.
Proof. Let , E be algebraic over F . Then F (, ) is a finite
extension of F . Since every element of F (, ) is algebraic over F ,
, , and / ( = 0) are all algebraic over F . Consequently,
the set of elements in E that are algebraic over F form a field.
325
326
21.2
Splitting Fields
3
root in the field Q( 3 ). However, this field is not a splitting field
for p(x) since the complex cube roots of 3,
3 3 ( 6 3 )5 i
,
2
are not in Q( 3 3 ).
Theorem 21.31. Let p(x) F [x] be a nonconstant polynomial.
Then there exists a splitting field E for p(x).
Proof. We will use mathematical induction on the degree of p(x).
If deg p(x) = 1, then p(x) is a linear polynomial and E = F .
Assume that the theorem is true for all polynomials of degree k
with 1 k < n and let deg p(x) = n. We can assume that p(x) is
irreducible; otherwise, by our induction hypothesis, we are done.
By Theorem 21.5, there exists a field K such that p(x) has a zero
1 in K. Hence, p(x) = (x 1 )q(x), where q(x) K[x]. Since
deg q(x) = n 1, there exists a splitting field E K of q(x) that
contains the zeros 2 , . . . , n of p(x) by our induction hypothesis.
Consequently,
E = K(2 , . . . , n ) = F (1 , . . . , n )
is a splitting field of p(x).
327
F [x]/q(x)
E()
F ()
328
E()
F ()
21.3
Geometric Constructions
In ancient Greece, three classic problems were posed. These problems are geometric in nature and involve straightedge-and-compass
constructions from what is now high school geometry; that is, we
are allowed to use only a straightedge and compass to solve them.
The problems can be stated as follows.
1. Given an arbitrary angle, can one trisect the angle into three
equal subangles using only a straightedge and compass?
329
Constructible Numbers
A real number is constructible if we can construct a line segment
of length || in a finite number of steps from a segment of unit
length by using a straightedge and compass.
Theorem 21.35. The set of all constructible real numbers forms
a subfield F of the field of real numbers.
330
C
x
is a con-
x
1
A
Proof. Let (x1 , y1 ) and (x2 , y2 ) be points on a line whose coordinates are in F . If x1 = x2 , then the equation of the line through
the two points is x x1 = 0, which has the form ax + by + c = 0.
331
332
x + y + dx + ey + f = 0.
If we eliminate y from these equations, we obtain an equation of
the form Ax2 + Bx + C = 0, where A, B, and C are in F . The x
coordinate of the intersection points is given by
B B 2 4AC
x=
2A
333
3
2 is a zero of the irreducible polynomial x3 2 over Q; hence,
3
[Q( 2 ) : Q] = 3
This is impossible, since 3 is not a power of 2.
Squaring the circle. Suppose that we have a circle of radius 1.
The area of the circle is ; therefore, we must be able to construct
Trisecting an Angle
Trisecting an arbitrary angle is impossible. We will show that it
is impossible to construct a 20 angle. Consequently, a 60 angle
cannot be trisected. We first need to calculate the triple-angle
formula for the cosine:
cos 3 = cos(2 + )
= cos 2 cos sin 2 sin
= (2 cos2 1) cos 2 sin2 cos
= (2 cos2 1) cos 2(1 cos2 ) cos
= 4 cos3 3 cos .
The angle can be constructed if and only if = cos is constructible. Let = 20 . Then cos 3 = cos 60 = 1/2. By the
triple-angle formula for the cosine,
1
43 3 = .
2
Therefore, is a zero of 8x3 6x1. This polynomial has no factors
in Z[x], and hence is irreducible over Q[x]. Thus, [Q() : Q] = 3.
Consequently, cannot be a constructible number.
Sage Extensions of the field of rational numbers are a central
object of study in number theory, so with Sages roots in this discipline, it is no surprise that there is extensive support for fields
and for extensions of the rationals. Sage also contains an implementation of the entire field of algebraic numbers, with exact representations.
Historical Note
Algebraic number theory uses the tools of algebra to solve problems in number theory. Modern algebraic number theory began
334
21.4
Exercises
(a)
1/3 + 7
(b) 3 + 3 5
(c) 3 + 2 i
(d) cos + i sin for = 2/n with n N
21.4. EXERCISES
(e)
335
3
2i
(c) Q( 2, i) over Q
(d) Q( 3, 5, 7 ) over Q
(e) Q( 2, 3 2 ) over Q
(f) Q( 8 ) over Q( 2 )
(h) Q( 2 + 5 ) over Q( 5 )
(i) Q( 2, 6 + 10 ) over Q( 3 + 5 )
3. Find the splitting field for each of the following polynomials.
(a) x4 10x2 + 21 over Q
(c) x3 + 2x + 2 over Z3
(b) x4 + 1 over Q
(d) x3 3 over Q
that [Q( 4 3, i) : Q] = 8.
336
337
21.5
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
22
Finite Fields
Finite fields appear in many applications of algebra, including coding theory and cryptography. We already know one finite field,
Zp , where p is prime. In this chapter we will show that a unique
finite field of order pn exists for every prime p, where n is a positive integer. Finite fields are also called Galois fields in honor of
variste Galois, who was one of the first mathematicians to investigate them.
22.1
339
ap + bp = (a + b)p
for all positive integers n.
p k pk
p
(a + b) =
a b .
k
k=0
( )
p
p!
=
k!(p k)!
k
(a+b)p
n+1
n+1
+bp
Therefore, the lemma is true for n+1 and the proof is complete.
Let F be a field. A polynomial f (x) F [x] of degree n is
separable if it has n distinct roots in the splitting field of f (x);
that is, f (x) is separable when it factors into distinct linear factors
over the splitting field of f . An extension E of F is a separable
extension of F if every element in E is the root of a separable
polynomial in F [x].
Example 22.4. The
x2 2 is separable
over Q since
polynomial
it factors as (x 2 )(x + 2 ).
In
fact,
Q(
2
)
is
a separable
340
Proof. Let f (x) be separable. Then f (x) factors over some extension field of F as f (x) = (x 1 )(x 2 ) (x n ), where
i = j for i = j. Taking the derivative of f (x), we see that
f (x) = (x 2 ) (x n )
+ (x 1 )(x 3 ) (x n )
+ + (x 1 ) (x n1 ).
Hence, f (x) and f (x) can have no common factors.
To prove the converse, we will show that the contrapositive of
the statement is true. Suppose that f (x) = (x )k g(x), where
k > 1. Differentiating, we have
f (x) = k(x )k1 g(x) + (x )k g (x).
Therefore, f (x) and f (x) have a common factor.
Theorem 22.6. For every prime p and every positive integer n,
there exists a finite field F with pn elements. Furthermore, any
n
field of order pn is isomorphic to the splitting field of xp x over
Zp .
n
341
GF(p12 )
GF(p4 )
GF(p6 )
GF(p2 )
GF(p3 )
GF(p)
where n = pe11 pekk and the p1 , . . . , pk are (not necessarily distinct) primes. Let m be the least common multiple of pe11 , . . . , pekk .
342
Then G contains an element of order m. Since every in G satisfies xr 1 for some r dividing m, must also be a root of xm 1.
Since xm 1 has at most m roots in F , n m. On the other hand,
we know that m |G|; therefore, m = n. Thus, G contains an
element of order n and must be cyclic.
Corollary 22.11. The multiplicative group of all nonzero elements
of a finite field is cyclic.
Corollary 22.12. Every finite extension E of a finite field F is a
simple extension of F .
Proof. Let be a generator for the cyclic group E of nonzero
elements of E. Then E = F ().
Example 22.13. The finite field GF(24 ) is isomorphic to the field
Z2 /1 + x + x4 . Therefore, the elements of GF(24 ) can be taken
to be
{a0 + a1 + a2 2 + a3 3 : ai Z2 and 1 + + 4 = 0}.
Remembering that 1 + + 4 = 0, we add and multiply elements
of GF(24 ) exactly as we add and multiply polynomials. The multiplicative group of GF(24 ) is isomorphic to Z15 with generator
:
1 =
6 = 2 + 3
11 = + 2 + 3
2 = 2
7 = 1 + + 3
12 = 1 + + 2 + 3
3 = 3
8 = 1 + 2
13 = 1 + 2 + 3
4 = 1 +
9 = + 3
14 = 1 + 3
5 = + 2
10 = 1 + + 2
15 = 1.
22.2
Polynomial Codes
343
1 0 0
1 0 0
1 1 0
0 1 0
1 1 1
0 0 1
and
G
=
G1 =
.
2
1 0 0
1 1 1
0 1 1
0 1 0
0 0 1
0 0 1
Messages in the first code are encoded as follows:
(000)
(001)
(010)
(011)
7
7
(000000)
(001001)
(010010)
(011011)
(100)
(101)
(110)
(111)
7
7
(100100)
(101101)
(110110)
(111111).
7
7
(000000)
(001111)
(011110)
(010001)
(100)
(101)
(110)
(111)
7
7
(111100)
(110011)
(100010)
(101101).
Polynomial Codes
We would like to find an easy method of obtaining cyclic linear
codes. To accomplish this, we can use our knowledge of finite
fields and polynomial rings over Z2 . Any binary n-tuple can be
interpreted as a polynomial in Z2 [x]. Stated another way, the ntuple (a0 , a1 , . . . , an1 ) corresponds to the polynomial
f (x) = a0 + a1 x + + an1 xn1 ,
where the degree of f (x) is at most n 1. For example, the polynomial corresponding to the 5-tuple (10011) is
1 + 0x + 0x2 + 1x3 + 1x4 = 1 + x3 + x4 .
Conversely, with any polynomial f (x) Z2 [x] with deg f (x) < n
we can associate a binary n-tuple. The polynomial x + x2 + x4
corresponds to the 5-tuple (01101).
Let us fix a nonconstant polynomial g(x) in Z2 [x] of degree
n k. We can define an (n, k)-code C in the following manner.
If (a0 , . . . , ak1 ) is a k-tuple to be encoded, then f (x) = a0 +
a1 x + + ak1 xk1 is the corresponding polynomial in Z2 [x]. To
344
1 0 0 1 0 0
H = 0 1 0 0 1 0 .
0 0 1 0 0 1
Since the smallest weight of any nonzero codeword is 2, this code
has the ability to detect all single errors.
Rings of polynomials have a great deal of structure; therefore,
our immediate goal is to establish a link between polynomial codes
and ring theory. Recall that xn 1 = (x 1)(xn1 + + x + 1).
The factor ring
Rn = Z2 [x]/xn 1
can be considered to be the ring of polynomials of the form
f (t) = a0 + a1 t + + an1 tn1
that satisfy the condition tn = 1. It is an easy exercise to show that
Zn2 and Rn are isomorphic as vector spaces. We will often identify
elements in Zn2 with elements in Z[x]/xn 1. In this manner we
can interpret a linear code as a subset of Z[x]/xn 1.
345
The additional ring structure on polynomial codes is very powerful in describing cyclic codes. A cyclic shift of an n-tuple can be
described by polynomial multiplication. If f (t) = a0 + a1 t + +
an1 tn1 is a code polynomial in Rn , then
tf (t) = an1 + a0 t + + an2 tn1
is the cyclically shifted word obtained from multiplying f (t) by
t. The following theorem gives a beautiful classification of cyclic
codes in terms of the ideals of Rn .
Theorem 22.16. A linear code C in Zn2 is cyclic if and only if it
is an ideal in Rn = Z[x]/xn 1.
Proof. Let C be a linear cyclic code and suppose that f (t) is in
C. Then tf (t) must also be in C. Consequently, tk f (t) is in C
for all k N. Since C is a linear code, any linear combination of
the codewords f (t), tf (t), t2 f (t), . . . , tn1 f (t) is also a codeword;
therefore, for every polynomial p(t), p(t)f (t) is in C. Hence, C is
an ideal.
Conversely, let C be an ideal in Z2 [x]/xn + 1. Suppose that
f (t) = a0 + a1 t + + an1 tn1 is a codeword in C. Then tf (t) is
a codeword in C; that is, (a1 , . . . , an1 , a0 ) is in C.
Theorem 22.16 tells us that knowing the ideals of Rn is equivalent to knowing the linear cyclic codes in Zn2 . Fortunately, the
ideals in Rn are easy to describe. The natural ring homomorphism
: Z2 [x] Rn defined by [f (x)] = f (t) is a surjective homomorphism. The kernel of is the ideal generated by xn 1. By
Theorem 16.34, every ideal C in Rn is of the form (I), where I
is an ideal in Z2 [x] that contains xn 1. By Theorem 17.20, we
know that every ideal I in Z2 [x] is a principal ideal, since Z2 is a
field. Therefore, I = g(x) for some unique monic polynomial in
Z2 [x]. Since xn 1 is contained in I, it must be the case that
g(x) divides xn 1. Consequently, every ideal C in Rn is of the
form
C = g(t) = {f (t)g(t) : f (t) Rn and g(x) | (xn 1) in Z2 [x]}.
The unique monic polynomial of the smallest degree that generates
C is called the minimal generator polynomial of C.
Example 22.17. If we factor x7 1 into irreducible components,
we have
x7 1 = (1 + x)(1 + x + x3 )(1 + x2 + x3 ).
We see that g(t) = (1+t+t3 ) generates an ideal C in R7 . This code
is a (7, 4)-block code. As in Example 22.15, it is easy to calculate a
346
1
1
G = 1
0
0
0
1
1
0
1
0
0
0
0
1
1
0
1
0
0
0
1 .
0
1
In general, we can determine a generator matrix for an (n, k)code C by the manner in which the elements tk are encoded. Let
xn 1 = g(x)h(x) in Z2 [x]. If g(x) = g0 + g1 x + + gnk xnk
and h(x) = h0 + h1 x + + hk xk , then the n k matrix
g0
0
g0
0
g1
.
..
..
..
..
.
.
.
G = gnk gnk1 g0
0
gnk g1
..
..
..
..
.
.
.
.
0
0
gnk
is a generator matrix for the code C with generator polynomial
g(t). The parity-check matrix for C is the (n k) n matrix
0 0
0 hk h0
0 0 hk h0 0
H=
.
hk h0 0
0 0
We will leave the details of the proof of the following proposition
as an exercise.
Proposition 22.18. Let C = g(t) be a cyclic code in Rn and
suppose that xn 1 = g(x)h(x). Then G and H are generator and
parity-check matrices for C, respectively. Furthermore, HG = 0.
Example 22.19. In Example 22.17,
x7 1 = g(x)h(x) = (1 + x + x3 )(1 + x + x2 + x4 ).
Therefore, a parity-check matrix for this code is
0 0 1 0 1 1 1
H = 0 1 0 1 1 1 0 .
1 0 1 1 1 0 0
347
To determine the error-detecting and error-correcting capabilities of a cyclic code, we need to know something about determinants. If 1 , . . . , n are elements in a field F , then the n n
matrix
1
1
1
1
2 n
2
22 n2
1
.
..
..
..
..
.
.
.
1n1 2n1 nn1
is called the Vandermonde matrix. The determinant of this
matrix is called the Vandermonde determinant. We will need
the following lemma in our investigation of cyclic codes.
Lemma 22.20. Let 1 , . . . , n be elements in a field F with n 2.
Then
det
1
1
12
..
.
..
.
1
2
22
..
.
1n1 2n1
1
n
n2
..
.
(i j ).
=
1j<in
nn1
p(x) = det
1
1
12
..
.
1
2
22
..
.
1n1 2n1
1
1
n1
x
2
n1 x2
.
..
..
..
.
.
.
n1
n1
n1 x
348
where
= (1)n+n det
1
1
12
..
.
1
2
22
..
.
1n2 2n2
1
n1
2
n1
.
.
..
.
.
.
n2
n1
(i j ).
1j<in1
349
Therefore, (ai0 , ai1 , . . . , ais1 ) is a solution to the homogeneous system of linear equations
( i0 )r x0 + ( i1 )r x1 + + ( is1 )r xn1 = 0
( i0 )r+1 x0 + ( i1 )r+1 x1 + + ( is1 )r+1 xn1 = 0
..
.
( i0 )r+s1 x0 + ( i1 )r+s1 x1 + + ( is1 )r+s1 xn1 = 0.
However, this system has a unique solution, since the determinant
of the matrix
( i0 )r
( i1 )r
( is1 )r
( i0 )r+1
( i1 )r+1 ( is1 )r+1
..
..
..
..
.
.
.
.
i
r+s1
i
r+s1
i
r+s1
( 0 )
( 1 )
( s1 )
can be shown to be nonzero using Lemma 22.20 and the basic properties of determinants (Exercise). Therefore, this solution must be
ai0 = ai1 = = ais1 = 0.
BCH Codes
Some of the most important codes, discovered independently by A.
Hocquenghem in 1959 and by R. C. Bose and D. V. Ray-Chaudhuri
in 1960, are BCH codes. The European and transatlantic communication systems both use BCH codes. Information words to be
encoded are of length 231, and a polynomial of degree 24 is used to
generate the code. Since 231 + 24 = 255 = 28 1, we are dealing
with a (255, 231)-block code. This BCH code will detect six errors
and has a failure rate of 1 in 16 million. One advantage of BCH
codes is that efficient error correction algorithms exist for them.
The idea behind BCH codes is to choose a generator polynomial
of smallest degree that has the largest error detection and error
correction capabilities. Let d = 2r + 1 for some r 0. Suppose
that is a primitive nth root of unity over Z2 , and let mi (x) be
the minimal polynomial over Z2 of i . If
g(x) = lcm[m1 (x), m2 (x), . . . , m2r (x)],
then the cyclic code g(t) in Rn is called the BCH code of length
n and distance d. By Theorem 22.21, the minimum distance of
C is at least d.
Theorem 22.22. Let C = g(t) be a cyclic code in Rn . The
following statements are equivalent.
1. The code C is a BCH code whose minimum distance is at
least d.
350
1
1
H = 1
.
..
2
3
..
.
2
4
6
..
.
1 2r 4r
..
.
n1
(n1)(2)
(n1)(3)
..
(n1)(2r)
Hx =
a0 + a1 + + an1 n1
a0 + a1 2 + + an1 ( 2 )n1
..
.
a0 + a1 2r + + an1 ( 2r )n1
f ()
f ( 2 )
= . =0
..
f ( 2r )
22.3. EXERCISES
351
0 0 0 0 0 0 0 1 1 0 1 0 0 0 1
0 0 0 0 0 0 1 1 0 1 0 0 0 1 0
0 0 0 0 0 1 1 0 1 0 0 0 1 0 0
0 0 0 0 1 1 0 1 0 0 0 1 0 0 0
.
0 0 0 1 1 0 1 0 0 0 1 0 0 0 0
0 0 1 1 0 1 0 0 0 1 0 0 0 0 0
0 1 1 0 1 0 0 0 1 0 0 0 0 0 0
1 1 0 1 0 0 0 1 0 0 0 0 0 0 0
Sage Finite fields are important in a variety of applied disciplines,
such as cryptography and coding theory (see introductions to these
topics in other chapters). Sage has excellent support for finite fields
allowing for a wide variety of computations.
22.3
Exercises
(c) x9 1
(d) x4 + x3 + x2 + x + 1
352
12. Prove or disprove: There exists a finite field that is algebraically closed.
13. Let p be prime. Prove that the field of rational functions Zp (x)
is an infinite field of characteristic p.
14. Let D be an integral domain of characteristic p. Prove that
n
n
n
(a b)p = ap bp for all a, b D.
15. Show that every element in a finite field can be written as the
sum of two squares.
16. Let E and F be subfields of a finite field K. If E is isomorphic
to F , show that E = F .
17. Let F E K be fields. If K is separable over F , show that
K is also separable over E.
18. Let E be an extension of a finite field F , where F has q elements. Let E be algebraic over F of degree n. Prove that
F () has q n elements.
19. Show that every finite extension of a finite field F is simple;
that is, if E is a finite extension of a finite field F , prove that there
exists an E such that E = F ().
20. Show that for every n there exists an irreducible polynomial
of degree n in Zp [x].
21. Prove that the Frobenius map : GF(pn ) GF(pn ) given
by : 7 p is an automorphism of order n.
22. Show that every element in GF(pn ) can be written in the form
ap for some unique a GF(pn ).
23. Let E and F be subfields of GF(pn ). If |E| = pr and |F | = ps ,
what is the order of E F ?
24. (Wilsons Theorem) Let p be prime. Prove that (p 1)! 1
(mod p).
g0
0
g0
0
g1
.
..
..
..
..
.
.
.
G = gnk gnk1 g0
0
gnk g1
..
..
..
..
.
.
.
.
0
0
gnk
and H to be the (n k) n matrix
0 0
0 hk h0
0 0 hk h0 0
H=
.
hk h0 0
0 0
(a) Prove that G is a generator matrix for C.
(b) Prove that H is a parity-check matrix for C.
(c) Show that HG = 0.
22.4
354
22.5
[1]
[2]
[3]
[4]
355
[5]
[6]
23
Galois Theory
A classic problem of algebra is to find the solutions of a polynomial equation. The solution to the quadratic equation was known
in antiquity. Italian mathematicians found general solutions to the
general cubic and quartic equations in the sixteenth century; however, attempts to solve the general fifth-degree, or quintic, polynomial were repulsed for the next three hundred years. Certainly,
equations such as x5 1 = 0 or x6 x3 6 = 0 could be solved, but
no solution like the quadratic formula was found for the general
quintic,
ax5 + bx4 + cx3 + dx2 + ex + f = 0.
Finally, at the beginning of the nineteenth century, Ruffini and
Abel both found quintics that could not be solved with any formula. It was Galois, however, who provided the full explanation
by showing which polynomials could and could not be solved by
formulas. He discovered the connection between groups and field
extensions. Galois theory demonstrates the strong interdependence
of group and field theory, and has had far-reaching implications beyond its original purpose.
In this chapter we will prove the Fundamental Theorem of Galois Theory. This result will be used to establish the insolvability of
the quintic and to prove the Fundamental Theorem of Algebra.
23.1
Field Automorphisms
Our first task is to establish a link between group theory and field
theory by examining automorphisms of fields.
Proposition 23.1. The set of all automorphisms of a field F is a
group under composition of functions.
357
Example 23.4. Consider
the fields Q Q( 5 ) Q( 3, 5 ).
Then for a, b Q( 5 ),
(a + b 3 ) = a b 3
(a + b 5 ) = a b 5
is an automorphism of Q( 3, 5) leaving
Q(
3 ) fixed. The au
tomorphism = moves both 3 and 5.
It
will soon be clear
that {id, , , } is the Galois group of Q( 3, 5 ) over Q. The
following table shows that this group is isomorphic to Z2 Z2 .
id
id id
id
id
id
We may also regard
the
field
Q( 3, 5 ) as a vector space over
Q
thathasbasis {1, 3, 5, 15 }. It is no coincidence that |G(Q( 3, 5 )/Q)| =
[Q( 3, 5 ) : Q)] = 4.
358
and 2 are conjugate over Q since they are both roots of the
irreducible polynomial x2 2.
A converse of the last proposition exists. The proof follows
directly from Lemma 21.32.
Proposition 23.6. If and are conjugate over F , there exists
an isomorphism : F () F () such that is the identity when
restricted to F .
Theorem 23.7. Let f (x) be a polynomial in F [x] and suppose that
E is the splitting field for f (x) over F . If f (x) has no repeated
roots, then
|G(E/F )| = [E : F ].
Proof. We will use mathematical induction on the degree of f (x).
If the degree of f (x) is 0 or 1, then E = F and there is nothing to
show. Assume that the result holds for all polynomials of degree
k with 0 k < n. Suppose that the degree of f (x) is n. Let p(x)
be an irreducible factor of f (x) of degree r. Since all of the roots
of p(x) are in E, we can choose one of these roots, say , so that
F F () E. Then
[E : F ()] = n/r
and
[F () : F ] = r.
359
( + ) = ( + )p = p + p = () + ()
by Lemma 22.3 Also, it is easy to show that () = ()().
Since is a nonzero homomorphism of fields, it must be injective.
It must also be onto, since E is a finite field. We know that must
n
be in G(E/F ), since F is the splitting field of xp x over the base
field of order p. This means that leaves every element in F fixed.
Finally, we must show that the order of is k. By Theorem 23.7,
we know that
nk
m
k () = p = p =
is the identity of G(E/F ). However, r cannot be the identity
nr
for 1 r < k; otherwise, xp x would have pm roots, which is
impossible.
Example
23.9. We can now confirm that the Galois group of
Q( 3, 5 ) over Q in Example 23.4 is indeed isomorphic toZ2 Z
2.
is a subgroup of G(Q( 3, 5 )/Q);
Certainly the group H = {id, , ,}
however, H must be all of G(Q( 3, 5 )/Q), since
|H| = [Q( 3, 5 ) : Q] = |G(Q( 3, 5 )/Q)| = 4.
Example 23.10. Let us compute the Galois group of
f (x) = x4 + x3 + x2 + x + 1
over Q. We know that f (x) is irreducible by Exercise 17.4.20 in
Chapter 17. Furthermore, since (x 1)f (x) = x5 1, we can use
360
Separable Extensions
Many of the results that we have just proven depend on the fact
that a polynomial f (x) in F [x] has no repeated roots in its splitting
field. It is evident that we need to know exactly when a polynomial
factors into distinct linear factors in its splitting field. Let E be
the splitting field of a polynomial f (x) in F [x]. Suppose that f (x)
factors over E as
f (x) = (x 1 )n1 (x 2 )n2 (x r )nr =
(x i )ni .
i=1
361
Q( 3, 5 ) = Q( 3 + 5 )
and
3
6
Q( 5, 5 i) = Q( 5 i).
i
j
23.2
362
363
364
Let E be an algebraic extension of F . If every irreducible polynomial in F [x] with a root in E has all of its roots in E, then
E is called a normal extension of F ; that is, every irreducible
polynomial in F [x] containing a root in E is the product of linear
factors in E[x].
Theorem 23.18. Let E be a field extension of F . Then the following statements are equivalent.
1. E is a finite, normal, separable extension of F .
2. E is a splitting field over F of a separable polynomial.
3. F = EG for some finite group G of automorphisms of E.
Proof. (1) (2). Let E be a finite, normal, separable extension
of F . By the Primitive Element Theorem, we can find an in E
such that E = F (). Let f (x) be the minimal polynomial of
over F . The field E must contain all of the roots of f (x) since it
is a normal extension F ; hence, E is a splitting field for f (x).
(2) (3). Let E be the splitting field over F of a separable polynomial. By Proposition 23.16, EG(E/F ) = F . Since
|G(E/F )| = [E : F ], this is a finite group.
(3) (1). Let F = EG for some finite group of automorphisms
G of E. Since [E : F ] |G|, E is a finite extension of F . To
show that E is a finite, normal extension of F , let f (x) F [x] be
an irreducible monic polynomial that has a root in E. We must
show that f (x) is the product of distinct linear factors in E[x]. By
Proposition 23.5, automorphisms in G permute the roots of f (x)
lying in E. Hence, if we let G act on , wecan obtain distinct
roots 1 = , 2 , . . . , n in E. Let g(x) = ni=1 (x i ). Then
g(x) is separable over F and g() = 0. Any automorphism in G
permutes the factors of g(x) since it permutes these roots; hence,
when acts on g(x), it must fix the coefficients of g(x). Therefore,
the coefficients of g(x) must be in F . Since deg g(x) deg f (x)
and f (x) is the minimal polynomial of , f (x) = g(x).
Corollary 23.19. Let K be a field extension of F such that F =
KG for some finite group of automorphisms G of K. Then G =
G(K/F ).
365
{id, , , }
{id, }
{id, }
{id, }
{id}
Q( 3 )
Q( 5 ) Q( 15 )
Figure 23.21: G(Q( 3, 5 )/Q)
We are now ready to state and prove the Fundamental Theorem
of Galois Theory.
Theorem 23.22 (Fundamental Theorem of Galois Theory). Let
F be a finite field or a field of characteristic zero. If E is a finite normal extension of F with Galois group G(E/F ), then the
following statements are true.
1. The map K 7 G(E/K) is a bijection of subfields K of E
containing F with the subgroups of G(E/F ).
2. If F K E, then
[E : K] = |G(E/K)| and [K : F ] = [G(E/F ) : G(E/K)].
3. F K L E if and only if {id} G(E/L) G(E/K)
G(E/F ).
4. K is a normal extension of F if and only if G(E/K) is a
normal subgroup of G(E/F ). In this case
G(K/F )
= G(E/F )/G(E/K).
366
{id}
G(E/L)
G(E/K)
G(E/F )
367
Example 23.24. In this example we will illustrate the Fundamental Theorem of Galois Theory by determining the lattice of
subgroups of the Galois group of f (x) = x4 2. We will compare
this lattice to the lattice of field extensions of Q that are contained
4
2, i).
in the splitting field of x4 2. The splitting field
of
f
(x)
is
Q(
2
2
To see this, notice that
f (x) factors
as (x + 2 )(x 2 ); hence,
4
4
Since [Q(
2 ) : Q] =4 and i is not in Q(
2 ), it must be the
4
4
4
case that [Q( 2, i) : Q( 2 )] = 2. Hence, [Q( 2, i) : Q] = 8. The
set
{1,
4
4
4
4
4
4
2, ( 2 )2 , ( 2 )3 , i, i 2, i( 2 )2 , i( 2 )3 }
4
is a basis of Q(
2, i) over Q. The lattice of field extensions of Q
4
contained in Q( 2, i) is illustrated in Figure 23.25(a).
The Galois group G of f
(x) mustbe of order 8. Let be the
automorphism defined by ( 4 2 ) = i 4 2 and (i) = i, and be the
automorphism defined by complex conjugation; that is, (i) = i.
Then G has an element of order 4 and an element of order 2. It
is easy to verify by direct computation that the elements of G are
{id, , 2 , 3 , , , 2 , 3 } and that the relations 2 = id, 4 =
id, and = 1 are satisfied; hence, G must be isomorphic to
D4 . The lattice of subgroups of G is illustrated in Figure 23.25(b).
368
Q( 4 2, i)
Q( 4 2 )
Q( 4 2 i)
Q( 2, i)
Q( 2 )
Q(i)
Q((1 + i) 4 2 ) Q((1 i) 4 2 )
Q( 2 i)
(a)
D4
{id, }
{id, 2 }
{id, 2 }
{id, }
{id}
{id, 3 }
(b)
Historical Note
Solutions for the cubic and quartic equations were discovered
in the 1500s. Attempts to find solutions for the quintic equations
puzzled some of historys best mathematicians. In 1798, P. Ruffini
submitted a paper that claimed no such solution could be found;
however, the paper was not well received. In 1826, Niels Henrik
Abel (18021829) finally offered the first correct proof that quintics
are not always solvable by radicals.
Abel inspired the work of variste Galois. Born in 1811, Galois began to display extraordinary mathematical talent at the age
of 14. He applied for entrance to the cole Polytechnique several
times; however, he had great difficulty meeting the formal entrance
requirements, and the examiners failed to recognize his mathematical genius. He was finally accepted at the cole Normale in 1829.
Galois worked to develop a theory of solvability for polynomials. In 1829, at the age of 17, Galois presented two papers on the
solution of algebraic equations to the Acadmie des Sciences de
23.3. APPLICATIONS
369
23.3
Applications
Solvability by Radicals
Throughout this section we shall assume that all fields have characteristic zero to ensure that irreducible polynomials do not have
multiple roots. The immediate goal of this section is to determine
when the roots of a polynomial f (x) can be computed with a finite
number of operations on the coefficients of f (x). The allowable
operations are addition, subtraction, multiplication, division, and
the extraction of nth roots. Certainly the solution to the quadratic
equation, ax2 + bx + c = 0, illustrates this process:
x=
b2 4ac
.
2a
The only one of these operations that might demand a larger field
is the taking of nth roots. We are led to the following definition.
An extension field E of a field F is an extension by radicals
if there exists a chain of subfields
F = F0 F1 F2 Fr = E
such for i = 1, 2, . . . , r, we have Fi = Fi1 (i ) and ini Fi1
for some positive integer ni . A polynomial f (x) is solvable by
radicals over F if the splitting field K of f (x) over F is contained
in an extension of F by radicals. Our goal is to arrive at criteria
that will tell us whether or not a polynomial f (x) is solvable by
radicals by examining the Galois group f (x).
The easiest polynomial to solve by radicals is one of the form
xn a. As we discussed in Chapter 4, the roots of xn 1 are
called the nth roots of unity. These roots are a finite subgroup
of the splitting field of xn 1. By Corollary 22.11, the nth roots
of unity form a cyclic group. Any generator of this group is called
a primitive nth root of unity.
370
2
n
(
+ i sin
2
n
)
.
23.3. APPLICATIONS
371
372
23.3. APPLICATIONS
373
60
5
3
40 f(x) = x 6x 27x3
20
-3
-2
-1
-20
-40
-60
Figure 23.31: The graph of f (x) = x5 6x3 27x 3
Example 23.32. We will show that f (x) = x5 6x3 27x 3
Q[x] is not solvable. We claim that the Galois group of f (x) over Q
is S5 . By Eisensteins Criterion, f (x) is irreducible and, therefore,
must be separable. The derivative of f (x) is f (x) = 5x4 18x2 27;
hence, setting f (x) = 0 and solving, we find that the only real roots
of f (x) are
6 6+9
.
x=
5
Therefore, f (x) can have at most one maximum and one minimum.
It is easy to show that f (x) changes sign between 3 and 2, between 2 and 0, and once again between 0 and 4 (Figure 23.31).
Therefore, f (x) has exactly three distinct real roots. The remaining two roots of f (x) must be complex conjugates. Let K be the
splitting field of f (x). Since f (x) has five distinct roots in K and
every automorphism of K fixing Q is determined by the way it
permutes the roots of f (x), we know that G(K/Q) is a subgroup
of S5 . Since f is irreducible, there is an element in G(K/Q)
such that (a) = b for two roots a and b of f (x). The automorphism of C that takes a + bi 7 a bi leaves the real roots fixed and
interchanges the complex roots; consequently, G(K/Q) S5 . By
Lemma 23.30, S5 is generated by a transposition and an element of
order 5; therefore, G(K/Q) must be all of S5 . By Theorem 10.11,
374
23.4. EXERCISES
375
23.4
Exercises
(d) G(Q( 2, 3 2, i)/Q)
(c) x4 + x2 + 1 over Z3
(d) x3 + x2 + 1 over Z2
x5 12x2 + 2
x5 4x4 + 2x + 2
x3 5
x4 x2 6
x5 + 1
(c) x4 2x2 15
(b) x4 8x2 + 15
(d) x3 2
376
xp 1
= xp1 + xp2 + + x + 1
x1
377
23.5
[1]
[2]
[3]
[4]
378
[5]
[6]
[7]
A
GNU Free
Documentation License
381
formats that can be read and edited only by proprietary word
processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated
HTML, PostScript or PDF produced by some word processors for
output purposes only.
The Title Page means, for a printed book, the title page
itself, plus such following pages as are needed to hold, legibly, the
material this License requires to appear in the title page. For works
in formats which do not have any title page as such, Title Page
means the text near the most prominent appearance of the works
title, preceding the beginning of the body of the text.
The publisher means any person or entity that distributes
copies of the Document to the public.
A section Entitled XYZ means a named subunit of the Document whose title either is precisely XYZ or contains XYZ in parentheses following text that translates XYZ in another language.
(Here XYZ stands for a specific section name mentioned below,
such as Acknowledgements, Dedications, Endorsements, or
History.) To Preserve the Title of such a section when you
modify the Document means that it remains a section Entitled
XYZ according to this definition.
The Document may include Warranty Disclaimers next to the
notice which states that this License applies to the Document.
These Warranty Disclaimers are considered to be included by reference in this License, but only as regards disclaiming warranties:
any other implication that these Warranty Disclaimers may have
is void and has no effect on the meaning of this License.
2. VERBATIM COPYING You may copy and distribute
the Document in any medium, either commercially or noncommercially, provided that this License, the copyright notices, and the
license notice saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use technical measures
to obstruct or control the reading or further copying of the copies
you make or distribute. However, you may accept compensation
in exchange for copies. If you distribute a large enough number of
copies you must also follow the conditions in section 3.
You may also lend copies, under the same conditions stated
above, and you may publicly display copies.
3. COPYING IN QUANTITY If you publish printed copies
(or copies in media that commonly have printed covers) of the
Document, numbering more than 100, and the Documents license
notice requires Cover Texts, you must enclose the copies in covers
that carry, clearly and legibly, all these Cover Texts: Front-Cover
Texts on the front cover, and Back-Cover Texts on the back cover.
383
if it has fewer than five), unless they release you from this
requirement.
3. State on the Title page the name of the publisher of the
Modified Version, as the publisher.
4. Preserve all the copyright notices of the Document.
5. Add an appropriate copyright notice for your modifications
adjacent to the other copyright notices.
6. Include, immediately after the copyright notices, a license notice giving the public permission to use the Modified Version
under the terms of this License, in the form shown in the
Addendum below.
7. Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Documents license notice.
8. Include an unaltered copy of this License.
9. Preserve the section Entitled History, Preserve its Title,
and add to it an item stating at least the title, year, new
authors, and publisher of the Modified Version as given on
the Title Page. If there is no section Entitled History in
the Document, create one stating the title, year, authors, and
publisher of the Document as given on its Title Page, then
add an item describing the Modified Version as stated in the
previous sentence.
10. Preserve the network location, if any, given in the Document
for public access to a Transparent copy of the Document,
and likewise the network locations given in the Document
for previous versions it was based on. These may be placed
in the History section. You may omit a network location
for a work that was published at least four years before the
Document itself, or if the original publisher of the version it
refers to gives permission.
11. For any section Entitled Acknowledgements or Dedications, Preserve the Title of the section, and preserve in the
section all the substance and tone of each of the contributor
acknowledgements and/or dedications given therein.
12. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the
equivalent are not considered part of the section titles.
13. Delete any section Entitled Endorsements. Such a section
may not be included in the Modified Version.
385
Entitled History; likewise combine any sections Entitled Acknowledgements, and any sections Entitled Dedications. You
must delete all sections Entitled Endorsements.
6. COLLECTIONS OF DOCUMENTS You may make a
collection consisting of the Document and other documents released
under this License, and replace the individual copies of this License
in the various documents with a single copy that is included in the
collection, provided that you follow the rules of this License for
verbatim copying of each of the documents in all other respects.
You may extract a single document from such a collection, and
distribute it individually under this License, provided you insert a
copy of this License into the extracted document, and follow this
License in all other respects regarding verbatim copying of that
document.
7. AGGREGATION WITH INDEPENDENT WORKS
A compilation of the Document or its derivatives with other separate and independent documents or works, in or on a volume of
a storage or distribution medium, is called an aggregate if the
copyright resulting from the compilation is not used to limit the
legal rights of the compilations users beyond what the individual
works permit. When the Document is included in an aggregate,
this License does not apply to the other works in the aggregate
which are not themselves derivative works of the Document.
If the Cover Text requirement of section 3 is applicable to these
copies of the Document, then if the Document is less than one half
of the entire aggregate, the Documents Cover Texts may be placed
on covers that bracket the Document within the aggregate, or the
electronic equivalent of covers if the Document is in electronic form.
Otherwise they must appear on printed covers that bracket the
whole aggregate.
8. TRANSLATION Translation is considered a kind of modification, so you may distribute translations of the Document under
the terms of section 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but
you may include translations of some or all Invariant Sections in
addition to the original versions of these Invariant Sections. You
may include a translation of this License, and all the license notices in the Document, and any Warranty Disclaimers, provided
that you also include the original English version of this License
and the original versions of those notices and disclaimers. In case
of a disagreement between the translation and the original version
of this License or a notice or disclaimer, the original version will
prevail.
387
11. RELICENSING Massive Multiauthor Collaboration Site
(or MMC Site) means any World Wide Web server that publishes
copyrightable works and also provides prominent facilities for anybody to edit those works. A public wiki that anybody can edit is an
example of such a server. A Massive Multiauthor Collaboration
(or MMC) contained in the site means any set of copyrightable
works thus published on the MMC site.
CC-BY-SA means the Creative Commons Attribution-Share
Alike 3.0 license published by Creative Commons Corporation, a
not-for-profit corporation with a principal place of business in San
Francisco, California, as well as future copyleft versions of that
license published by that same organization.
Incorporate means to publish or republish a Document, in
whole or in part, as part of another Document.
An MMC is eligible for relicensing if it is licensed under this
License, and if all works that were first published under this License
somewhere other than this MMC, and subsequently incorporated in
whole or in part into the MMC, (1) had no cover texts or invariant
sections, and (2) were thus incorporated prior to November 1, 2008.
The operator of an MMC Site may republish an MMC contained in the site under CC-BY-SA on the same site at any time
before August 1, 2009, provided the MMC is eligible for relicensing.
ADDENDUM: How to use this License for your documents To use this License in a document you have written, include a copy of the License in the document and put the following
copyright and license notices just after the title page:
Copyright YEAR YOUR NAME
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free
Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with
no Invariant Sections, no Front-Cover Texts, and no
Back-Cover Texts. A copy of the license is included
in the section entitled GNU Free Documentation License.
If you have Invariant Sections, Front-Cover Texts and BackCover Texts, replace the with Texts. line with this:
with the Invariant Sections being LIST THEIR TITLES, with the Front-Cover Texts being LIST, and
with the Back-Cover Texts being LIST.
If you have Invariant Sections without Cover Texts, or some
other combination of the three, merge those two alternatives to
suit the situation.
1.3 Exercises
1. (a) A B = {2}; (b) B C = {5}.
2. (a) AB = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), (c, 1), (c, 2), (c, 3)};
(d) A D = .
6. If x A (B C), then either x A or x B C. Thus,
x A B and A C. Hence, x (A B) (A C). Therefore,
A(B C) (AB)(AC). Conversely, if x (AB)(AC),
then x A B and A C. Thus, x A or x is in both B and C.
So x A (B C) and therefore (A B) (A C) A (B C).
Hence, A (B C) = (A B) (A C).
10. (A B) (A \ B) (B \ A) = (A B) (A B ) (B A ) =
[A(B B )](B A ) = A(B A ) = (AB)(AA ) = AB.
14. A \ (B C) = A (B C) = (A A) (B C ) = (A
B ) (A C ) = (A \ B) (A \ C).
17. (a) Not a map since f (2/3) is undefined; (b) this is a map;
(c) not a map, since f (1/2) = 3/4 but f (2/4) = 3/8; (d) this is a
map.
18. (a) f is one-to-one but not onto. f (R) = {x R : x > 0}.
(c) f is neither one-to-one nor onto. f (R) = {x : 1 x 1}.
20. (a) f (n) = n + 1.
22. (a) Let x, y A. Then g(f (x)) = (g f )(x) = (g f )(y) =
g(f (y)). Thus, f (x) = f (y) and x = y, so g f is one-to-one. (b)
Let c C, then c = (g f )(x) = g(f (x)) for some x A. Since
f (x) B, g is onto.
23. f 1 (x) = (x + 1)/(x 1).
24. (a) Let y f (A1 A2 ). Then there exists an x A1 A2 such
that f (x) = y. Hence, y f (A1 ) or f (A2 ). Therefore, y f (A1 )
f (A2 ). Consequently, f (A1 A2 ) f (A1 ) f (A2 ). Conversely, if
y f (A1 )f (A2 ), then y f (A1 ) or f (A2 ). Hence, there exists an
x in A1 or A2 such that f (x) = y. Thus, there exists an x A1 A2
389
2.3 Exercises
1. The base case, S(1) : [1(1 + 1)(2(1) + 1)]/6 = 1 = 12 is true.
Assume that S(k) : 12 + 22 + + k 2 = [k(k + 1)(2k + 1)]/6 is true.
Then
12 + 22 + + k 2 + (k + 1)2 = [k(k + 1)(2k + 1)]/6 + (k + 1)2
= [(k + 1)((k + 1) + 1)(2(k + 1) + 1)]/6,
and so S(k + 1) is true. Thus, S(n) is true for all positive integers
n.
3. The base case, S(4) : 4! = 24 > 16 = 24 is true. Assume
S(k) : k! > 2k is true. Then (k + 1)! = k!(k + 1) > 2k 2 = 2k+1 , so
S(k + 1) is true. Thus, S(n) is true for all positive integers n.
8. Follow the proof in Example 2.4.
11. The base case, S(0) : (1 + x)0 1 = 0 0 = 0 x is true.
Assume S(k) : (1 + x)k 1 kx is true. Then
(1 + x)k+1 1 = (1 + x)(1 + x)k 1
= (1 + x)k + x(1 + x)k 1
kx + x(1 + x)k
kx + x
= (k + 1)x,
so S(k + 1) is true. Therefore, S(n) is true for all positive integers
n.
17. For (a) and (b) use mathematical induction. (c) Show that
f1 = 1, f2 = 1, and fn+2 = fn+1 + fn . (d) Use part (c). (e) Use
part (b) and Exercise 2.3.16.
19. Use the Fundamental Theorem of Arithmetic.
23. Use the Principle of Well-Ordering and the division algorithm.
27. Since gcd(a, b) = 1, there exist integers r and s such that
ar + bs = 1. Thus, acr + bcs = c. Since a divides both bc and itself,
a must divide c.
29. Every prime must be of the form 2, 3, 6n + 1, or 6n + 5.
Suppose there are only finitely many primes of the form 6k + 5.
391
3.4 Exercises
1. (a) 3 + 7Z = {. . . , 4, 3, 10, . . .}; (c) 18 + 26Z; (e) 5 + 6Z.
2. (a) Not a group; (c) a group.
6.
1 5 7 11
1 1 5 7 11
5 5 1 11 7
7 7 11 1 5
11 11 7 5 1
8. Pick two matrices. Almost any pair will work.
15. There is a nonabelian group containing six elements.
16. Look at the symmetry group of an equilateral triangle or a
square.
17. The are five different groups of order 8.
18. Let
(
=
1 2 n
a1 a2 an
4.4 Exercises
1. (a) False; (c) false; (e) true.
2. (a) 12; (c) infinite; (e) 10.
5.3 Exercises
1. (a) (12453); (c) (13)(25).
2. (a) (135)(24); (c) (14)(23); (e) (1324); (g) (134)(25); (n) (17352).
3. (a) (16)(15)(13)(14); (c) (16)(14)(12).
4. (a1 , a2 , . . . , an )1 = (a1 , an , an1 , . . . , a2 )
5. (a) {(13), (13)(24), (132), (134), (1324), (1342)} is not a subgroup.
8. (12345)(678).
11. Permutations of the form
(1), (a1 , a2 )(a3 , a4 ), (a1 , a2 , a3 ), (a1 , a2 , a3 , a4 , a5 )
are possible for A5 .
17. Calculate (123)(12) and (12)(123).
25. Consider the cases (ab)(bc) and (ab)(cd).
30. For (a), show that 1 ((ai )) = (ai+1 ).
393
6.4 Exercises
1. The order of g and the order h must both divide the order of
G.
2. The possible orders must divide 60.
3. This is true for every proper nontrivial subgroup.
4. False.
5. (a) 8, 1 + 8, 2 + 8, 3 + 8, 4 + 8, 5 + 8, 6 + 8, and
7 + 8; (c) 3Z, 1 + 3Z, and 2 + 3Z.
7. 4(15) 48 1 (mod 15).
12. Let g1 gH. Show that g1 Hg and thus gH Hg.
19. Show that g(H K) = gH gK.
22. If gcd(m, n) = 1, then (mn) = (m)(n) (Exercise 2.3.26
in Chapter 2).
7.3 Exercises
1. LAORYHAPDWK
3. Hint: V = E, E = X (also used for spaces and punctuation),
K = R.
4. 26! 1
7. (a) 2791; (c) 112135 25032 442.
9. (a) 31; (c) 14.
10. (a) n = 11 41; (c) n = 8779 4327.
8.5 Exercises
2. This cannot be a group code since (0000)
/ C.
3. (a) 2; (c) 2.
4. (a) 3; (c) 4.
6. (a) dmin = 2; (c) dmin = 1.
7.
(a) (00000), (00101), (10011), (10110)
0
0
G = 1
0
1
1
0
1
1
1 0
0 1
1 0
G=
1 1
0 1
1 1
9. Multiple errors occur in one of the received words.
11. (a) A canonical parity-check matrix with standard generator
matrix
1
1
G = 0 .
0
1
(c) A canonical parity-check matrix with standard generator
matrix
1 0
0 1
G=
.
1 1
1 0
12. (a) All possible syndromes occur.
15. (a) C, (10000) + C, (01000) + C, (00100) + C, (00010) + C,
(11000) + C, (01100) + C, (01010) + C. A decoding table does not
exist for C since this is only a single error-detecting code.
19. Let x C have odd weight and define a map from the set of
odd codewords to the set of even codewords by y 7 x + y. Show
that this map is a bijection.
23. For 20 information positions, at least 6 check bits are needed
to ensure an error-correcting code.
9.3 Exercises
1. Every infinite cyclic group is isomorphic to Z by Theorem 9.7.
2. Define : C GL2 (R) by
(
(a + bi) =
)
a b
.
b a
3. False.
6. Define a map from Zn into the nth roots of unity by k 7
cis(2k/n).
395
8. Assume that Q is cyclic and try to find a generator.
11. There are two nonabelian and three abelian groups that are
not isomorphic.
16. (a) 12; (c) 5.
19. Draw the picture.
20. True.
25. True.
27. Let a be a generator for G. If : G H is an isomorphism,
show that (a) is a generator for H.
38. Any automorphism of Z6 must send 1 to another generator
of Z6 .
45. To show that is one-to-one, let g1 = h1 k1 and g2 = h2 k2
and consider (g1 ) = (g2 ).
10.3 Exercises
1. (a)
A4
(12)A4
A4
(12)A4
A4
(12)A4
(12)A4
A4
11.3 Exercises
2. (a) is a homomorphism with kernel {0}; (c) is not a homomorphism.
12.3 Exercises
1.
] 1[
]
1[
x + y2 + x2 y2 =
x + y, x + y x2 y2
2
2
]
1[
=
x2 + 2x, y + y2 x2 y2
2
= x, y.
3. (a) is in SO(2); (c) is not in O(3).
5. (a) x, y = y, x.
7. Use the unimodular matrix
(
)
5 2
.
2 1
10. Show that the kernel of the map det : O(n) R is SO(n).
13. True.
17. p6m
13.3 Exercises
1. There are three possible groups.
4. (a) {0} 6 3 Z12 ; (e) {(1)}{0} {(1), (123), (132)}
{0} S3 {0} S3 2 S3 Z4 .
7. Use the Fundamental Theorem of Finitely Generated Abelian
Groups.
397
12. If N and G/N are solvable, then they have solvable series
N = Nn Nn1 N1 N0 = {e}
G/N = Gn /N Gn1 /N G1 /N G0 /N = {N }.
16. Use the fact that Dn has a cyclic subgroup of index 2.
21. G/G is abelian.
14.4 Exercises
1. Example 14.1: 0, R2 \ {0}. Example 14.2: X = {1, 2, 3, 4}.
2. (a) X(1) = {1, 2, 3}, X(12) = {3}, X(13) = {2}, X(23) = {1},
X(123) = X(132) = . G1 = {(1), (23)}, G2 = {(1), (13)}, G3 =
{(1), (12)}.
3. (a) O1 = O2 = O3 = {1, 2, 3}.
6. The conjugacy classes for S4 are
O(1) = {(1)},
O(12) = {(12), (13), (14), (23), (24), (34)},
O(12)(34) = {(12)(34), (13)(24), (14)(23)},
O(123) = {(123), (132), (124), (142), (134), (143), (234), (243)},
O(1234) = {(1234), (1243), (1324), (1342), (1423), (1432)}.
The class equation is 1 + 3 + 6 + 6 + 8 = 24.
8. (34 + 31 + 32 + 31 + 32 + 32 + 33 + 33 )/8 = 21.
11. The group of rigid motions of the cube can be described by
the allowable permutations of the six faces and is isomorphic to
S4 . There are the identity cycle, 6 permutations with the structure
(abcd) that correspond to the quarter turns, 3 permutations with
the structure (ab)(cd) that correspond to the half turns, 6 permutations with the structure (ab)(cd)(ef ) that correspond to rotating
the cube about the centers of opposite edges, and 8 permutations
with the structure (abc)(def ) that correspond to rotating the cube
about opposite vertices.
15. (1 26 + 3 24 + 4 23 + 2 22 + 2 21 )/12 = 13.
17. (1 28 + 3 26 + 2 24 )/6 = 80.
22. Use the fact that x gC(a)g 1 if and only if g 1 xg C(a).
15.3 Exercises
1. If |G| = 18 = 2 32 , then the order of a Sylow 2-subgroup is 2,
and the order of a Sylow 3-subgroup is 9.
2. The four Sylow 3-subgroups of S4 are P1 = {(1), (123), (132)},
P2 = {(1), (124), (142)}, P3 = {(1), (134), (143)}, P4 = {(1), (234), (243)}.
16.6 Exercises
8. False. Assume
there is an isomorphism : Q( 2 ) Q( 3 )
such that ( 2 ) = a.
13. (a) x 17 (mod 55); (c) x 214 (mod 2772).
16. If I = {0}, show that 1 I.
18. (a) (a)(b) = (ab) = (ba) = (b)(a).
26. Let a R with a = 0. Then the principal ideal generated by
a is R. Thus, there exists a b R such that ab = 1.
28. Compute (a + b)2 and (ab)2 .
34. Let a/b, c/d Z(p) . Then a/b + c/d = (ad + bc)/bd and (a/b)
(c/d) = (ac)/(bd) are both in Z(p) , since gcd(bd, p) = 1.
38. Suppose that x2 = x and x = 0. Since R is an integral
domain, x = 1. To find a nontrivial idempotent, look in M2 (R).
399
17.4 Exercises
2. (a) 9x2 + 2x + 5; (b) 8x4 + 7x3 + 2x2 + 7x.
3. (a) 5x3 + 6x2 3x + 4 = (5x2 + 2x + 1)(x 2) + 6; (c) 4x5
x3 + x2 + 4 = (4x2 + 4)(x3 + 3) + 4x2 + 2.
5. (a) No zeros in Z12 ; (c) 3, 4.
7. Look at (2x + 1).
8. (a) Reducible; (c) irreducible.
10. One factorization is x2 + x + 8 = (x + 2)(x + 9).
13. The integers Z do not form a field.
14. False.
16. Let : R S be an isomorphism. Define : R[x] S[x]
by (a0 + a1 x + + an xn ) = (a0 ) + (a1 )x + + (an )xn .
20. The polynomial
n (x) =
xn 1
= xn1 + xn2 + + x + 1
x1
is called the cyclotomic polynomial. Show that p (x) is irreducible over Q for any prime p.
26. Find a nontrivial proper ideal in F [x].
18.3 Exercises
19.4 Exercises
2.
10
15
1
5. False.
6. (a) (a b a ) a
a
a
b
a
(c) a (a b)
a
a
8. Not equivalent.
10. (a) a [(a b ) b] = a (a b).
14. Let I, J be ideals in R. We need to show that I + J = {r + s :
r I and s J} is the smallest ideal in R containing both I and
J. If r1 , r2 I and s1 , s2 J, then (r1 + s1 ) + (r2 + s2 ) = (r1 +
r2 ) + (s1 + s2 ) is in I + J. For a R, a(r1 + s1 ) = ar1 + as1 I + J;
hence, I + J is an ideal in R.
18. (a) No.
20. (). a = b (ab )(a b) = (aa )(a a) = OO = O.
(). (a b ) (a b) = O a b = (a a) b = a (a b) =
a [I (a b)] = a [(a a ) (a b)] = [a (a b )] [a (a b)] =
a [(a b ) (a b)] = a 0 = a. A symmetric argument shows
that a b = b.
20.4 Exercises
3.
5.
7.
(d)
Q( 2, 3 ) has basis {1, 2, 3, 6 } over Q.
The set {1, x, x2 , . . . , xn1 } is a basis for Pn .
(a) Subspace of dimension 2 with basis {(1, 0, 3), (0, 1, 2)};
not a subspace
401
10. Since 0 = 0 = (v + v) = (v) + v, it follows that
v = (v).
12. Let v0 = 0, v1 , . . . , vn V and 0 = 0, 1 , . . . , n F . Then
0 v0 + + n vn = 0.
15. (a) Let u, v ker(T ) and F . Then
T (u + v) = T (u) + T (v) = 0
T (v) = T (v) = 0 = 0.
Hence, u + v, v ker(T ), and ker(T ) is a subspace of V .
(c) The statement that T (u) = T (v) is equivalent to T (u v) =
T (u) T (v) = 0, which is true if and only if u v = 0 or u = v.
17. (a) Let u, u U and v, v V . Then
(u + v) + (u + v ) = (u + u ) + (v + v ) U + V
(u + v) = u + v U + V.
21.4 Exercises
1. (a) x4 (2/3)x2 62/9; (c) x4 2x2 + 25.
2. (a) {1, 2, 3, 6 }; (c) {1, i, 2, 2 i}; (e) {1, 21/6 , 21/3 , 21/2 , 22/3 , 25/6 }.
3. (a) Q( 3, 7 ).
5. Use the fact that the elements of Z2 [x]/x3 + x + 1 are 0, 1, ,
1+, 2 , 1+2 , +2 , 1++2 and the fact that 3 ++1 = 0.
8. False.
14. Suppose that E is algebraic over F and K is algebraic over
E. Let K. It suffices to show that is algebraic over some
finite extension of F . Since is algebraic over E, it must be the
zero of some polynomial p(x) = 0 + 1 x + + n xn in E[x].
Hence is algebraic over F (0 , . . . , n ).
22. Since
21 }
is a basis for Q( 3, 7 )
over Q, Q( 3, 7 )
{1, 3, 7,
Q( 3 + 7 ). Since [Q( 3, 7 ) : Q] = 4, [Q( 3 + 7 ) :Q] = 2
or
4. Since
of
the degree
22.3 Exercises
1. Make sure that you have a field extension.
4. There are eight elements in Z2 (). Exhibit two more zeros of
x3 + x2 + 1 other than in these eight elements.
5. Find an irreducible polynomial p(x) in Z3 [x] of degree 3 and
show that Z3 [x]/p(x) has 27 elements.
7. (a) x5 1 = (x + 1)(x4 + x3 + x2 + x + 1); (c) x9 1 =
(x + 1)(x2 + x + 1)(x6 + x3 + 1).
8. True.
11. (a) Use the fact that x7 1 = (x + 1)(x3 + x + 1)(x3 + x2 + 1).
12. False.
17. If p(x) F [x], then p(x) E[x].
18. Since is algebraic over F of degree n, we can write any
element F () uniquely as = a0 + a1 + + an1 n1 with
ai F . There are q n possible n-tuples (a0 , a1 , . . . , an1 ).
24. Factor xp1 1 over Zp .
23.4 Exercises
1.
2.
(c)
3.
(a) Z2 ; (c) Z2 Z2 Z2 .
(a) Separable over Q since x3 +2x2 x2 = (x1)(x+1)(x+2);
not separable over Z3 since x4 + x2 + 1 = (x + 1)2 (x + 2)2 .
If
403
where ai Q. Prove that i is an isomorphism of fields.
Show that 2 generates G(Q()/Q).
(c) Show that {, 2 , . . . , p1 } is a basis for Q() over Q, and
consider which linear combinations of , 2 , . . . , p1 are left
fixed by all elements of G(Q()/Q).
Notation
The following table defines the notation used in this book. Page
numbers or references refer to the first appearance of each symbol.
Symbol
Description
aA
N
Z
Q
R
C
AB
AB
AB
A
A\B
AB
An
id
f 1
a b (mod n)
n!
(n )
a is in the set A
4
the natural numbers
5
the integers
5
the rational numbers
5
the real numbers
5
the complex numbers
5
A is a subset of B
5
the empty set
5
the union of sets A and B
5
the intersection of sets A and B
5
complement of the set A
6
difference between sets A and B
6
Cartesian product of sets A and B
7
A A (n times)
8
identity mapping
11
inverse of the function f
11
a is congruent to b modulo n
15
n factorial
22
binomial coefficient n!/(k!(n k)!)
22
a divides b
25
greatest common divisor of a and b
25
power set of X
30
the least common multiple of m and n
31
the integers modulo n
34
group of units in Zn
41
the n n matrices with entries in R
41
the determinant of A
41
the general linear group
42
the group of quaternions
42
(Continued on next page)
a|b
gcd(a, b)
P(X)
lcm(m, n)
Zn
U (n)
Mn (R)
det A
GLn (R)
Q8
404
Page
405
Symbol
Description
Page
C
|G|
R
Q
SLn (R)
Z(G)
a
|a|
cis
T
Sn
(a1 , a2 , . . . , ak )
An
Dn
[G : H]
LH
RH
d(x, y)
dmin
w(x)
Mmn (Z2 )
Null(H)
ij
G
=H
Aut(G)
ig
Inn(G)
g
G/N
G
ker
(aij )
O(n)
x
SO(n)
E(n)
Ox
Xg
Gx
N (H)
H
Z[i]
Description
char R
Z(p)
deg f (x)
R[x]
R[x1 , x2 , . . . , xn ]
Q(x)
(a)
F (x)
F (x1 , . . . , xn )
ab
ab
ab
I
O
a
dim V
U V
Hom(V, W )
V
F (1 , . . . , n )
[E : F ]
GF(pn )
F
G(E/F )
F{i }
FG
2
characteristic of a ring R
ring of integers localized at p
degree of a polynomial
ring of polynomials over a ring R
ring of polynomials in n indeterminants
evaluation homomorphism at
field of rational functions over Q
Euclidean valuation of a
field of rational functions in x
field of rational functions in x1 , . . . , xn
a is less than b
join of a and b
meet of a and b
largest element in a lattice
smallest element in a lattice
complement of a in a lattice
dimension of a vector space V
direct sum of vector spaces U and V
set of all linear transformations from U into V
dual of a vector space V
smallest field containing F and 1 , . . . , n
dimension of a field extension of E over F
Galois field of order pn
multiplicative group of a field F
Galois group of E over F
field fixed by the automorphism i
field fixed by the automorphism group G
discriminant of a polynomial
Page
232
248
252
252
255
255
275
279
285
285
288
290
290
292
292
292
310
312
313
313
318
321
340
341
357
362
362
377
Index
G-equivalent, 199
G-set, 198
nth root of unity, 62, 369
RSA cryptosystem, 99
Abel, Niels Henrik, 368
Abelian group, 40
Adleman, L., 99
Algebraic closure, 325
Algebraic extension, 318
Algebraic number, 318
Algorithm
Euclidean, 27
Ascending chain condition, 277
Associate elements, 275
Atom, 295
Automorphism
inner, 166
Basis of a lattice, 179
Bieberbach, L., 183
Binary operation, 39
Binary symmetric channel, 111
Boole, George, 300
Boolean algebra
atom in a, 295
definition of, 293
finite, 295
isomorphism, 295
Boolean function, 208, 303
Burnside, William, 45, 155, 210
Cancellation law
for groups, 44
Cardano, Gerolamo, 264
Carmichael numbers, 105
Cauchys Theorem, 215
Cauchy, Augustin-Louis, 79
Cayley table, 40
Cayley, Arthur, 139
Centralizer
of a subgroup, 202
Characteristic of a ring, 232
Cipher, 95
Ciphertext, 95
Circuit
parallel, 298
series, 298
series-parallel, 299
Class equation, 202
Code
BCH, 349
cyclic, 342
group, 116
linear, 118
minimum distance of, 113
polynomial, 344
Commutative diagrams, 162
Commutative rings, 228
Composite integer, 27
Composition series, 192
Congruence modulo n, 15
Conjugacy classes, 202
Conjugate elements, 358
Conjugate, complex, 59
Conjugation, 199
Constructible number, 329
Coset
leader, 127
left, 87
representative, 87
right, 87
Coset decoding, 126
Cryptanalysis, 96
Cryptosystem
407
408
RSA, 99
affine, 97
definition of, 95
monoalphabetic, 97
polyalphabetic, 97
private key, 96
public key, 95
single key, 96
Cycle
definition of, 73
disjoint, 74
INDEX
Euclidean inner product, 172
Euclidean valuation, 279
Euler -function, 91
Euler, Leonhard, 92, 334
Extension
algebraic, 318
field, 315
finite, 321
normal, 364
radical, 369
separable, 339, 360
simple, 318
External direct product, 140
De Morgans laws
for Boolean algebras, 295
De Morgan, Augustus, 300
Faltings, Gerd, 334
Decoding table, 127
Feit, W., 155, 211
Deligne, Pierre, 334
Fermats factorizationalgorithm,
Derivative, 339
104
Determinant, Vandermonde, 347
Fermat, Pierre de, 92, 334
Dickson, L. E., 155
Ferrari, Ludovico, 265
Diffie, W., 98
Ferro, Scipione del, 264
Direct product of groups
Field, 228
external, 140
algebraically closed, 325
internal, 143
base, 315
Discriminant
extension, 315
of the cubic equation, 269
fixed, 362
of the quadratic equation, 268
Galois, 340
Division ring, 228
of fractions, 274
Domain
of quotients, 274
Euclidean, 279
splitting, 326
principal ideal, 276
Finitely generated group, 188
unique factorization, 275
Fior, Antonio, 264
Doubling the cube, 332
Fixed point set, 200
Function
Element
bijective, 9
associate, 275
Boolean, 208, 303
identity, 40
composition of, 9
inverse, 40
definition of, 8
irreducible, 275
domain of, 8
order of, 56
identity, 11
prime, 275
injective, 9
primitive, 361
invertible, 11
transcendental, 318
one-to-one, 9
Equivalence class, 14
onto, 9
Equivalence relation, 13
range of, 8
Euclidean algorithm, 27
surjective, 9
Euclidean domain, 279
Euclidean group, 175
switching, 208, 303
INDEX
Galois field, 340
Galois group, 357
Galois, variste, 44, 368
Gauss, Karl Friedrich, 283
Gaussian integers, 231
Generator of a cyclic subgroup,
56
Generators for a group, 188
Glide reflection, 176
Gorenstein, Daniel, 155
Greatest common divisor
of two integers, 25
of two polynomials, 258
Greatest lower bound, 290
Greiss, R., 155
Grothendieck, Alexander, 334
Group
p-group, 188, 215
abelian, 40
action, 198
alternating, 78
center of, 202
circle, 62
commutative, 40
cyclic, 56
definition of, 39
dihedral, 79
Euclidean, 175
factor, 150
finite, 42
finitely generated, 188
Galois, 357
general linear, 42, 171
generators of, 188
homomorphism of, 158
infinite, 42
isomorphic, 135
isomorphism of, 135
nonabelian, 40
noncommutative, 40
of units, 41
order of, 42
orthogonal, 172
permutation, 72
point, 180
quaternion, 42
quotient, 150
simple, 152, 155
409
solvable, 194
space, 180
special linear, 46, 171
special orthogonal, 175
symmetric, 71
symmetry, 177
Gdel, Kurt, 300
Hamming distance, 113
Hamming, R., 115
Hellman, M., 98
Hilbert, David, 183, 239, 300,
334
Homomorphic image, 158
Homomorphism
canonical, 161, 236
evaluation, 234, 255
kernel of a group, 160
kernel of a ring, 233
natural, 161, 236
of groups, 158
ring, 233
Ideal
definition of, 234
maximal, 237
one-sided, 235
prime, 238
principal, 235
trivial, 234
two-sided, 235
Indeterminate, 252
Index of a subgroup, 89
Infimum, 290
Inner product, 117
Integral domain, 228
Internal direct product, 143
International standard book number, 53
Irreducible element, 275
Irreducible polynomial, 259
Isometry, 176
Isomorphism
of Boolean algebras, 295
of groups, 135
ring, 233
Join, 290
Jordan, C., 155
410
Kernel
of a group homomorphism,
160
of a ring homomorphism, 233
Key
definition of, 95
private, 96
public, 95
single, 96
Klein, Felix, 45, 168, 239
Kronecker delta, 122, 173
Kronecker, Leopold, 334
Kummer, Ernst, 334
INDEX
Maximum-likelihood decoding, 111
Meet, 290
Minimal generator polynomial, 345
Minimal polynomial, 319
Minkowski, Hermann, 334
Monic polynomial, 252
Mordell-Weil conjecture, 334
Multiplicity of a root, 360
INDEX
separable, 360
zero of, 257
Polynomial separable, 339
Poset
definition of, 288
largest element in, 292
smallest element in, 292
Power set, 289
Prime element, 275
Prime ideal, 238
Prime integer, 27
Primitive nth root of unity, 63,
369
Primitive element, 361
Primitive polynomial, 281
Principal ideal, 235
Principal ideal domain (PID), 276
Principal series, 192
Pseudoprime, 105
Quaternions, 42, 230
Resolvent cubic equation, 270
Rigid motion, 37, 176
Ring
characteristic of, 232
commutative, 228
definition of, 227
division, 228
factor, 236
homomorphism, 233
isomorphism, 233
Noetherian, 277
quotient, 236
with identity, 228
with unity, 228
Rivest, R., 99
Ruffini, P., 368
Russell, Bertrand, 300
Scalar product, 305
Shamir, A., 99
Shannon, C.., 115
Simple extension, 318
Simple group, 152
Simple root, 360
Solvability by radicals, 369
Spanning set, 307
Splitting field, 326
411
Squaring the circle is impossible,
333
Standard decoding, 126
Subgroup
p-subgroup, 215
centralizer, 202
commutator, 220
cyclic, 56
definition of, 45
index of, 89
isotropy, 200
normal, 149
normalizer of, 217
proper, 45
stabilizer, 200
Sylowp-subgroup, 217
translation, 180
trivial, 45
Subnormal series of a group, 191
Subring, 230
Supremum, 290
Switch
closed, 298
definition of, 298
open, 298
Switching function, 208, 303
Sylow p-subgroup, 217
Sylow, Ludvig, 219
Syndrome of a code, 125, 354
Tartaglia, 264
Thompson, J., 155, 211
Transcendental element, 318
Transcendental number, 318
Transposition, 76
Trisection of an angle, 333
Unique factorization domain (UFD),
275
Unit, 228, 275
Universal Product Code, 52
Upper bound, 290
Vandermonde determinant, 347
Vandermonde matrix, 347
Vector space
basis of, 309
definition of, 305
dimension of, 310
412
INDEX
subspace of, 307