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