《计算机问题求解》课程参考书籍教材：Abstract Algebra - Theory and Applications（Thomas W. Judson）

Abstract Algebra Theory and Applications Thomas W.Judson Stephen F.Austin State University Sage Exercises for Abstract Algebra Robert A.Beezer University of Puget Sound Traduccion al espanol Antonio Behn Universidad de Chile August 1,2018

Abstract Algebra Theory and Applications Thomas W. Judson Stephen F. Austin State University Sage Exercises for Abstract Algebra Robert A. Beezer University of Puget Sound Traducción al español Antonio Behn Universidad de Chile August 1, 2018

Contents Acknowledgements Preface vi 1 Preliminaries 1 1.1 A Short Note on Proofs 1 1.2 Sets and Equivalence Relations... 3 1.3 Exercises 13 References and Suggested Readings 15 1.4 Sage 16 1.5 Sage Exercises 。。。 20 2 The Integers 22 2.1 Mathematical Induction.. 2.2 The Division Algorithm 的 2.3 Exercises 2.4 Programming Exercises 31 References and Suggested Readings.. 31 2.5Sage...············ 31 2.6 Sage Exercises 35 3 Groups 36 3.1 Integer Equivalence Classes and Symmetries..... 36 3.2 Definitions and Examples 40 3.3 Subgroups.·.················· 。 45 3.4 Exercises 47 3.5 Additional Exercises:Detecting Errors:········ 50 References and Suggested Readings..、..············· 51 52 3.7 Sage Exercises 57 4 Cyclic Groups 59 4.1 Cyclic Subgroups············· 59 4.2 Multiplicative Group of Complex Numbers........... 62 4.3 The Method of Repeated Squares...·············· 65 4.4 Exercises····························· 67 4.5 Programming Exercises·:··.···················: 70 References and Suggested Readings..................... 70 71 ⅸ

Contents Acknowledgements v Preface vi 1 Preliminaries 1 1.1 A Short Note on Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Sets and Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.5 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 The Integers 22 2.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2 The Division Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.5 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.6 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3 Groups 36 3.1 Integer Equivalence Classes and Symmetries . . . . . . . . . . . . . . . . . . 36 3.2 Definitions and Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.5 Additional Exercises: Detecting Errors . . . . . . . . . . . . . . . . . . . . . 50 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.6 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.7 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4 Cyclic Groups 59 4.1 Cyclic Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Multiplicative Group of Complex Numbers . . . . . . . . . . . . . . . . . . 62 4.3 The Method of Repeated Squares . . . . . . . . . . . . . . . . . . . . . . . . 65 4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.5 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.6 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 ix

CONTENTS 4.7 Sage Exercises··.···· 79 5 Permutation Groups 81 5.1 Definitions and Notation... 81 5.2 Dihedral Groups 87 5.3 Exercises 91 5.4 Sage 94 5.5 Sage Exercises 100 6 Cosets and Lagrange's Theorem 102 6.1 Cosets...·.....·.···.· ·。。 102 6.2 Lagrange's Theorem 104 6.3 Fermat's and Euler's Theorems. 105 6.4 Exercises 106 6.5Sage.············ 108 6.6 Sage Exercises 111 7 Introduction to Cryptography 114 7.1 Private Key Cryptography.··.·· 114 7.2 Public Key Cryptography 116 7.3 Exercises 119 7.4 Additional Exercises:Primality and Factoring...·····.·· 121 References and Suggested Readings..··..············· 122 122 7.6 Sage Exercises 126 8 Algebraic Coding Theory 127 8.1 Error-Detecting and Correcting Codes 127 8.2 Linear Codes.... 133 8.3 Parity-Check and Generator Matrices 136 8.4 Efficient Decoding 141 8.5 Exercises.············ 144 8.6 Programming Exercises 148 References and Suggested Readings.. 148 8.7Sage··············· 148 8.8 Sage Exercises······· 151 9 Isomorphisms 153 9.1 Definition and Examples ..... 153 9.2 Direct Products...... 。 157 9.3 Exercises 160 9.4 Sage 163 9.5 Sage Exercises 。。 167 10 Normal Subgroups and Factor Groups 169 10.1 Factor Groups and Normal Subgroups 169 10.2 The Simplicity of the Alternating Group . 171 l0.3 Exercises...················· 174 175 10.5 Sage Exercises ............. 179

x CONTENTS 4.7 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5 Permutation Groups 81 5.1 Definitions and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.2 Dihedral Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.4 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5.5 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6 Cosets and Lagrange’s Theorem 102 6.1 Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.2 Lagrange’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.3 Fermat’s and Euler’s Theorems . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.5 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.6 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 7 Introduction to Cryptography 114 7.1 Private Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 7.2 Public Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 7.4 Additional Exercises: Primality and Factoring . . . . . . . . . . . . . . . . . 121 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 122 7.5 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 7.6 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 8 Algebraic Coding Theory 127 8.1 Error-Detecting and Correcting Codes . . . . . . . . . . . . . . . . . . . . . 127 8.2 Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 8.3 Parity-Check and Generator Matrices . . . . . . . . . . . . . . . . . . . . . 136 8.4 Efficient Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 8.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 8.6 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 148 8.7 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 8.8 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 9 Isomorphisms 153 9.1 Definition and Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 9.2 Direct Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 9.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 9.4 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 9.5 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 10 Normal Subgroups and Factor Groups 169 10.1 Factor Groups and Normal Subgroups . . . . . . . . . . . . . . . . . . . . . 169 10.2 The Simplicity of the Alternating Group . . . . . . . . . . . . . . . . . . . . 171 10.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 10.4 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 10.5 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

CONTENTS xi 11 Homomorphisms 181 11.1 Group Homomorphisms..·····. 181 ll.2 The Isomorphism Theorems······ 183 11.3 Exercises 186 11.4 Additional Exercises:Automorphisms 187 11.5Sage...·..·····…···· 188 11.6 Sage Exercises 192 12 Matrix Groups and Symmetry 194 12.1 Matrix Groups 194 12.2 Symmetry 200 12.3 Exercises 206 References and Suggested Readings. 208 12.4Sage.············ 209 12.5 Sage Exercises 209 13 The Structure of Groups 210 13.1 Finite Abelian Groups 210 13.2 Solvable Groups 214 l3.3 Exercises··,······· 217 13.4 Programming Exercises 218 References and Suggested Readings.. 219 13.5Sage..············ 219 13.6 Sage Exercises ....... 221 14 Group Actions 222 14.1 Groups Acting on Sets 222 14.2 The Class Equation 225 14.3 Burnside's Counting Theorem.. 226 14.4 Exercises.·.·.·····.· 232 14.5 Programming Exercise .... 234 References and Suggested Reading 234 14.6Sage......·.. 235 14.7 Sage Exercises 238 15 The Sylow Theorems 240 15.1 The Sylow Theorems ... 240 15.2 Examples and Applications 243 15.3 Exercises 246 15.4 A Project 247 References and Suggested Readings.. 248 15.5Sage·..··············· 248 l5.6 Sage Exercises··.······ 254 16 Rings 256 16.1 Rings..·· 256 16.2 Integral Domains and Fields.. 259 16.3 Ring Homomorphisms and Ideals 261 l6.4 Maximal and Prime Ideals........·.......·.··. 264 16.5 An Application to Software Design 266 l6.6 Exercises...························· 269

CONTENTS xi 11 Homomorphisms 181 11.1 Group Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 11.2 The Isomorphism Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 11.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 11.4 Additional Exercises: Automorphisms . . . . . . . . . . . . . . . . . . . . . 187 11.5 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.6 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 12 Matrix Groups and Symmetry 194 12.1 Matrix Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 12.2 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 12.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 208 12.4 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 12.5 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 13 The Structure of Groups 210 13.1 Finite Abelian Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 13.2 Solvable Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 13.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 13.4 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 219 13.5 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 13.6 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 14 Group Actions 222 14.1 Groups Acting on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 14.2 The Class Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 14.3 Burnside’s Counting Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 226 14.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 14.5 Programming Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 References and Suggested Reading . . . . . . . . . . . . . . . . . . . . . . . . . . 234 14.6 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 14.7 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 15 The Sylow Theorems 240 15.1 The Sylow Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 15.2 Examples and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 15.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 15.4 A Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 248 15.5 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 15.6 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 16 Rings 256 16.1 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 16.2 Integral Domains and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 16.3 Ring Homomorphisms and Ideals . . . . . . . . . . . . . . . . . . . . . . . . 261 16.4 Maximal and Prime Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 16.5 An Application to Software Design . . . . . . . . . . . . . . . . . . . . . . . 266 16.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

xij CONTENTS l6.7 Programming Exercise·.····· 273 References and Suggested Readings.... 273 16.8 Sage 274 16.9 Sage Exercises 282 17 Polynomials 283 17.1 Polynomial Rings .. 283 17.2 The Division Algorithm 286 17.3 Irreducible Polynomials 289 17.4 Exercises 294 17.5 Additional Exercises:Solving the Cubic and Quartic Equations 296 17.6Sage...·.····· 298 17.7 Sage Exercises 303 18 Integral Domains 304 18.1 Fields of Fractions ...... 304 18.2 Factorization in Integral Domains........ 307 l8.3 Exercises················· 314 References and Suggested Readings..·· 316 18.4 Sage 316 18.5 Sage Exercises 319 19 Lattices and Boolean Algebras 320 19.1 Lattices.·· 320 19.2 Boolean Algebras......... 323 19.3 The Algebra of Electrical Circuits.... 328 19.4 Exercises··.········· 330 19.5 Programming Exercises 332 References and Suggested Readings.. 333 19.6Sage.············· 333 19.7 Sage Exercises 338 20 Vector Spaces 340 20.1 Definitions and Examples 340 20.2 Subspaces...:...·.··· 341 20.3 Linear Independence..... 342 20.4 Exercises 344 References and Suggested Readings.. 346 20.5Sage......·..····· 347 20.6 Sage Exercises 351 21 Fields 354 21.1 Extension Fields 354 21.2 Splitting Fields 362 21.3 Geometric Constructions 365 21.4 Exercises.·.······· 369 References and Suggested Readings.. 371 21.5Sage.·.················ 371 21.6 Sage Exercises........... 378

xii CONTENTS 16.7 Programming Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 273 16.8 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 16.9 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 17 Polynomials 283 17.1 Polynomial Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 17.2 The Division Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 17.3 Irreducible Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 17.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 17.5 Additional Exercises: Solving the Cubic and Quartic Equations . . . . . . . 296 17.6 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 17.7 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 18 Integral Domains 304 18.1 Fields of Fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 18.2 Factorization in Integral Domains . . . . . . . . . . . . . . . . . . . . . . . . 307 18.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 316 18.4 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 18.5 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 19 Lattices and Boolean Algebras 320 19.1 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 19.2 Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 19.3 The Algebra of Electrical Circuits . . . . . . . . . . . . . . . . . . . . . . . . 328 19.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 19.5 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 333 19.6 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 19.7 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 20 Vector Spaces 340 20.1 Definitions and Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 20.2 Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 20.3 Linear Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 20.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 346 20.5 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 20.6 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 21 Fields 354 21.1 Extension Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 21.2 Splitting Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 21.3 Geometric Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 21.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 371 21.5 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 21.6 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378

CONTENTS xiii 22 Finite Fields 380 22.1 Structure of a Finite Field....·...··..··. 380 22.2 Polynomial Codes 384 22.3 Exercises 390 22.4 Additional Exercises:Error Correction for BCH Codes 392 References and Suggested Readings.········· 393 22.5 Sage 393 22.6 Sage Exercises 395 23 Galois Theory 397 23.1 Field Automorphisms 397 23.2 The Fundamental Theorem 401 23.3 Applications.....·...··. 407 23.4 Exercises 411 References and Suggested Readings 413 23.5 Sage 414 23.6 Sage Exercises 424 A GNU Free Documentation License 427 B Hints and Solutions to Selected Exercises 434 C Notation 448 Index 451

CONTENTS xiii 22 Finite Fields 380 22.1 Structure of a Finite Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 22.2 Polynomial Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 22.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390 22.4 Additional Exercises: Error Correction for BCH Codes . . . . . . . . . . . . 392 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 393 22.5 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 22.6 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 23 Galois Theory 397 23.1 Field Automorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 23.2 The Fundamental Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 401 23.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407 23.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 References and Suggested Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 413 23.5 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414 23.6 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424 A GNU Free Documentation License 427 B Hints and Solutions to Selected Exercises 434 C Notation 448 Index 451

Preliminaries A certain amount of mathematical maturity is necessary to find and study applications of abstract algebra.A basic knowledge of set theory,mathematical induction,equivalence relations,and matrices is a must.Even more important is the ability to read and understand mathematical proofs.In this chapter we will outline the background needed for a course in abstract algebra. 1.1 A Short Note on Proofs Abstract mathematics is different from other sciences.In laboratory sciences such as chem- istry and physics,scientists perform experiments to discover new principles and verify theo- ries.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 argu- ments.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 =4. ·Ifax2+br+c=0anda≠0，then x=-b±VP-4ac 2a ·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 68,an argument that would satisfy anyone.Of course,audiences 1

1 Preliminaries A certain amount of mathematical maturity is necessary to find and study applications of abstract algebra. A basic knowledge of set theory, mathematical induction, equivalence relations, and matrices is a must. Even more important is the ability to read and understand mathematical proofs. In this chapter we will outline the background needed for a course in abstract algebra. 1.1 A Short Note on Proofs Abstract mathematics is different from other sciences. In laboratory sciences such as chem￾istry and physics, scientists perform experiments to discover new principles and verify theo￾ries. 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 argu￾ments. 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 x = −b ± √ b 2 − 4ac 2a . • x 3 − 4x 2 + 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 1

2 CHAPTER 1.PRELIMINARIES 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 one's 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 g is known as the conclusion.Consider the following statement:If a.x2+bx+c=0anda≠0，then x=-b±V6-4ac 2a The hypothesis is ax2+bx+c=0 and a0;the conclusion is x=-b±V-4ac 2a Notice that the statement says nothing about whether or not the hypothesis is true.How- ever,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 x2+0x=- a a b /b12 b 2 22 a 2a/ 2a a b 2 62-4ac z+ 2a 4a2 b ±V2-4ac E十 2a 2a -b±v2-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. Some Cautions and Suggestions There are several different strategies for proving propositions.In addition to using different methods of proof,students often make some common mistakes when they are first learning how to prove theorems.To aid students who are studying abstract mathematics for the

2 CHAPTER 1. PRELIMINARIES 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 one’s 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 = −b ± √ b 2 − 4ac 2a . The hypothesis is ax2 + bx + c = 0 and a ̸= 0; the conclusion is x = −b ± √ b 2 − 4ac 2a . Notice that the statement says nothing about whether or not the hypothesis is true. How￾ever, 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 x 2 + b a x = − c a x 2 + b a x + ( b 2a )2 = ( b 2a )2 − c a ( x + b 2a )2 = b 2 − 4ac 4a 2 x + b 2a = ± √ b 2 − 4ac 2a x = −b ± √ b 2 − 4ac 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. Some Cautions and Suggestions There are several different strategies for proving propositions. In addition to using different methods of proof, students often make some common mistakes when they are first learning how to prove theorems. To aid students who are studying abstract mathematics for the

1.2.SETS AND EQUIVALENCE RELATIONS 3 first time,we list here some of the difficulties that they may encounter and some of the strategies of proof available to them.It is a good idea to keep referring back to this list as a reminder.(Other techniques of proof will become apparent throughout this chapter and the remainder of the text.) A theorem cannot be proved by example;however,the standard way to show that a statement is not a theorem is to provide a counterexample. Quantifiers are important.Words and phrases such as only,for all,for every,and for some possess different meanings. Never assume any hypothesis that is not explicitly stated in the theorem.You cannot take things for granted. Suppose you wish to show that an object exists and is unigue.First show that there actually is such an object.To show that it is unique,assume that there are two such objects,say r and s,and then show that r =s. Sometimes it is easier to prove the contrapositive of a statement.Proving the state- ment "If p,then g"is exactly the same as proving the statement "If not g,then not p.” Although it is usually better to find a direct proof of a theorem,this task can some- times 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 interconnected- much more so than they may seem at first appearance. 1.2 Sets and Equivalence Relations 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 z whether or not z 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 aA. 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 r belongs to the set.We might write X={c1,x2,,n} for a set containing elements x1,x2,...,n or X ={xx 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 E=fx:x is an even integer and x >0h

1.2. SETS AND EQUIVALENCE RELATIONS 3 first time, we list here some of the difficulties that they may encounter and some of the strategies of proof available to them. It is a good idea to keep referring back to this list as a reminder. (Other techniques of proof will become apparent throughout this chapter and the remainder of the text.) • A theorem cannot be proved by example; however, the standard way to show that a statement is not a theorem is to provide a counterexample. • Quantifiers are important. Words and phrases such as only, for all, for every, and for some possess different meanings. • Never assume any hypothesis that is not explicitly stated in the theorem. You cannot take things for granted. • Suppose you wish to show that an object exists and is unique. First show that there actually is such an object. To show that it is unique, assume that there are two such objects, say r and s, and then show that r = s. • Sometimes it is easier to prove the contrapositive of a statement. Proving the state￾ment “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 some￾times 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 interconnected— much more so than they may seem at first appearance. 1.2 Sets and Equivalence Relations 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 E = {x : x is an even integer and x > 0}

CHAPTER 1.PRELIMINARIES We write 2 EE when we want to say that 2 is in the set E,and-3E to say that -3 is not in the set E. Some of the more important sets that we will consider are the following: N={nn is a natural number}={1,2,3,...}; Z={nn is an integer}={...,-1,0,1,2,...}; Q={rr is a rational number}=fp/q:p,gZ where 0); R=fx:z is a real number}; C=fz: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 AC B or B A,if every element of A is also an element of B. For example, {4,5,8}C{2,3,4,5,6,7,8,9} and NCZCQCRCC. Trivially,every set is a subset of itself.A set B is a proper subset of a set A if B C A but B A.If A is not a subset of B,we write A B;for example,(4,7,9}d (2,4,5,8,9}. Two sets are equal,written A B,if we can show that A C B and B C A. It is convenient to have a set with no elements in it.This set is called the empty set and is denoted by 0.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 AUB of two sets A and B is defined as AUB={x:x∈Aorx∈B}: the intersection of A and B is defined by AnB={x:x∈A and x∈B}: IfA={1,3,5}andB={1,2,3,9},then AUB={1,2,3,5,9}andA∩B={1,3} We can consider the union and the intersection of more than two sets.In this case we write UAi=A1 U...UAn i=1 and ∩A=An..nAn i=1 for the union and intersection,respectively,of the sets A1,...,An. When two sets have no elements in common,they are said to be disjoint;for example, if E is the set of even integers and O is the set of odd integers,then E and O are disjoint. Two sets A and B are disjoint exactly when An B=0. Sometimes we will work within one fixed set U,called the universal set.For any set A CU,we define the complement of A,denoted by A',to be the set A'={x:x∈U and x A}: We define the difference of two sets A and B to be A\B=AnB={x:x∈A and z年B}

4 CHAPTER 1. PRELIMINARIES We write 2 ∈ E when we want to say that 2 is in the set E, and −3 /∈ E to say that −3 is not in the set E. 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} and A ∩ B = {1, 3}. We can consider the union and the intersection of more than two sets. In this case we write ∪n i=1 Ai = A1 ∪ . . . ∪ An and ∩n i=1 Ai = A1 ∩ . . . ∩ An for the union and intersection, respectively, of the sets A1, . . . , An. When two sets have no elements in common, they are said to be disjoint; for example, if E is the set of even integers and O is the set of odd integers, then E and O are disjoint. Two sets A and B are disjoint exactly when A ∩ B = ∅. Sometimes we will work within one fixed set U, called the universal set. For any set A ⊂ U, we define the complement of A, denoted by A′ , to be the set A ′ = {x : x ∈ U and x ∈/ A}. We define the difference of two sets A and B to be A \ B = A ∩ B ′ = {x : x ∈ A and x ∈/ B}