Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 A Short Note on Proofs . . . . . . . . . . . . . . . . . . . . . 1
1.2 Sets and Equivalence Relations . . . . . . . . . . . . . . . . . 4
2 The Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . 23
2.2 The Division Algorithm . . . . . . . . . . . . . . . . . . . . . 27
3 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1 Integer Equivalence Classes and Symmetries . . . . . . . . . . 37
3.2 Definitions and Examples . . . . . . . . . . . . . . . . . . . . 42
3.3 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4 Cyclic Groups. . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1 Cyclic Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2 Multiplicative Group of Complex Numbers . . . . . . . . . . 63
4.3 The Method of Repeated Squares . . . . . . . . . . . . . . . . 68
5 Permutation Groups. . . . . . . . . . . . . . . . . . . . . . . . 76
5.1 Definitions and Notation . . . . . . . . . . . . . . . . . . . . . 77
5.2 Dihedral Groups . . . . . . . . . . . . . . . . . . . . . . . . . 85
6 Cosets and Lagrange's Theorem. . . . . . . . . . . . . . . . . . . . . 94
6.1 Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.2 Lagrange's Theorem . . . . . . . . . . . . . . . . . . . . . . . 97
6.3 Fermat's and Euler's Theorems . . . . . . . . . . . . . . . . . 99
7 Introduction to Cryptography. . . . . . . . . . . . . . . . . . . 102
7.1 Private Key Cryptography . . . . . . . . . . . . . . . . . . . . 103
7.2 Public Key Cryptography . . . . . . . . . . . . . . . . . . . . 106
8 Algebraic Coding Theory . . . . . . . . . . . . . . . . . . . . 113
8.1 Error-Detecting and Correcting Codes . . . . . . . . . . . . . 113
8.2 Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
8.3 Parity-Check and Generator Matrices . . . . . . . . . . . . . 126
8.4 Efficient Decoding . . . . . . . . . . . . . . . . . . . . . . . . 133
9 Isomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
9.1 Definition and Examples . . . . . . . . . . . . . . . . . . . . . 142
9.2 Direct Products . . . . . . . . . . . . . . . . . . . . . . . . . . 147
10 Normal Subgroups and Factor Groups 156
10.1 Factor Groups and Normal Subgroups . . . . . . . . . . . . . 156
10.2 The Simplicity of the Alternating Group . . . . . . . . . . . . 159
11 Homomorphisms. . . . . . . . . . . . . . . . . . . . . . . . . 166
11.1 Group Homomorphisms . . . . . . . . . . . . . . . . . . . . . 166
11.2 The Isomorphism Theorems . . . . . . . . . . . . . . . . . . . 169
12 Matrix Groups and Symmetry . . . . . . . . . . . . . . . . . . . 176
12.1 Matrix Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 176
12.2 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
13 The Structure of Groups . . . . . . . . . . . . . . . . . . . . . . 197
13.1 Finite Abelian Groups . . . . . . . . . . . . . . . . . . . . . . 197
13.2 Solvable Groups . . . . . . . . . . . . . . . . . . . . . . . . . 202
14 Group Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
14.1 Groups Acting on Sets . . . . . . . . . . . . . . . . . . . . . . 210
14.2 The Class Equation . . . . . . . . . . . . . . . . . . . . . . . 214
14.3 Burnside's Counting Theorem . . . . . . . . . . . . . . . . . . 216
15 The Sylow Theorems . . . . . . . . . . . . . . . . . . . . . . . . 228
15.1 The Sylow Theorems . . . . . . . . . . . . . . . . . . . . . . . 228
15.2 Examples and Applications . . . . . . . . . . . . . . . . . . . 232
16 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
16.1 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
16.2 Integral Domains and Fields . . . . . . . . . . . . . . . . . . . 245
16.3 Ring Homomorphisms and Ideals . . . . . . . . . . . . . . . . 247
16.4 Maximal and Prime Ideals . . . . . . . . . . . . . . . . . . . . 251
16.5 An Application to Software Design . . . . . . . . . . . . . . . 254
17 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
17.1 Polynomial Rings . . . . . . . . . . . . . . . . . . . . . . . . . 265
17.2 The Division Algorithm . . . . . . . . . . . . . . . . . . . . . 269
17.3 Irreducible Polynomials . . . . . . . . . . . . . . . . . . . . . 273
18 Integral Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
18.1 Fields of Fractions . . . . . . . . . . . . . . . . . . . . . . . . 284
18.2 Factorization in Integral Domains . . . . . . . . . . . . . . . . 288
19 Lattices and Boolean Algebras . . . . . . . . . . . . . . . . . . . . . 302
19.1 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
19.2 Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . 307
19.3 The Algebra of Electrical Circuits . . . . . . . . . . . . . . . . 313
20 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 320
20.1 Definitions and Examples . . . . . . . . . . . . . . . . . . . . 320
20.2 Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
20.3 Linear Independence . . . . . . . . . . . . . . . . . . . . . . . 323
21 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
21.1 Extension Fields . . . . . . . . . . . . . . . . . . . . . . . . . 330
21.2 Splitting Fields . . . . . . . . . . . . . . . . . . . . . . . . . . 341
21.3 Geometric Constructions . . . . . . . . . . . . . . . . . . . . . 344
22 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
22.1 Structure of a Finite Field . . . . . . . . . . . . . . . . . . . . 354
22.2 Polynomial Codes . . . . . . . . . . . . . . . . . . . . . . . . 359
23 Galois Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 372
23.1 Field Automorphisms . . . . . . . . . . . . . . . . . . . . . . 372
23.2 The Fundamental Theorem . . . . . . . . . . . . . . . . . . . 378
23.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
Hints and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
GNU Free Documentation License . . . . . . . . . . . . . . . . . . . . . . 410
Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
· · · · · · (收起)