This page intentionally left blank INTRODUCTION TO ABSTRACT ALGEBRA C0637_FM.indd 1 7/7/08 2:00:08 PM TEXTBOOKS in MATHEMATICS Series Editor: Denny Gulick PUBLISHED TITLES COMPLEX VARIABLES: A PHYSICAL APPROACH WITH APPLICATIONS AND MATLAB® Steven G. Krantz INTRODUCTION TO ABSTRACT ALGEBRA Jonathan D. H. Smith LINEAR ALBEBRA: A FIRST COURSE WITH APPLICATIONS Larry E. Knop FORTHCOMING TITLES ENCOUNTERS WITH CHAOS AND FRACTALS Denny Gulick C0637_FM.indd 2 7/7/08 2:00:09 PM TEXTBOOKS in MATHEMATICS INTRODUCTION TO ABSTRACT ALGEBRA Jonathan D. H. Smith Iowa State University Ames, Iowa, U.S.A. C0637_FM.indd 3 7/7/08 2:00:09 PM Chapman & Hall/CRC Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2009 by Taylor & Francis Group, LLC Chapman & Hall/CRC is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Printed in the United States of America on acid-free paper 10 9 8 7 6 5 4 3 2 1 International Standard Book Number-13: 978-1-4200-6371-4 (Hardcover) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher can- not assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copy- right.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that pro- vides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Library of Congress Cataloging-in-Publication Data Smith, Jonathan D. H., 1949- Introduction to abstract algebra / Jonathan D.H. Smith. p. cm. -- (Textbooks in mathematics ; 3) Includes bibliographical references and index. ISBN 978-1-4200-6371-4 (hardback : alk. paper) 1. Algebra, Abstract. I. Title. QA162.S62 2008 512’.02--dc22 2008027689 Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com C0637_FM.indd 4 7/7/08 2:00:09 PM Contents 1 NUMBERS 1 1.1 Ordering numbers . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 The Well-Ordering Principle . . . . . . . . . . . . . . . . . 3 1.3 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 The Division Algorithm . . . . . . . . . . . . . . . . . . . . 6 1.5 Greatest common divisors . . . . . . . . . . . . . . . . . . . 9 1.6 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . 10 1.7 Primes and irreducibles . . . . . . . . . . . . . . . . . . . . 13 1.8 The Fundamental Theorem of Arithmetic . . . . . . . . . . 14 1.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.10 Study projects . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.11 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2 FUNCTIONS 25 2.1 Specifying functions . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Composite functions . . . . . . . . . . . . . . . . . . . . . . 27 2.3 Linear functions . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 Semigroups of functions . . . . . . . . . . . . . . . . . . . . 29 2.5 Injectivity and surjectivity . . . . . . . . . . . . . . . . . . 31 2.6 Isomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.7 Groups of permutations . . . . . . . . . . . . . . . . . . . . 36 2.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.9 Study projects . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.10 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3 EQUIVALENCE 49 3.1 Kernel and equivalence relations . . . . . . . . . . . . . . . 49 3.2 Equivalence classes . . . . . . . . . . . . . . . . . . . . . . . 51 3.3 Rational numbers . . . . . . . . . . . . . . . . . . . . . . . 53 3.4 The First Isomorphism Theorem for Sets . . . . . . . . . . 56 3.5 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . 58 3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.7 Study projects . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.8 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 v vi 4 GROUPS AND MONOIDS 67 4.1 Semigroups . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.2 Monoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.3 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.4 Componentwise structure . . . . . . . . . . . . . . . . . . . 73 4.5 Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.6 Submonoids and subgroups . . . . . . . . . . . . . . . . . . 78 4.7 Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.8 Multiplication tables . . . . . . . . . . . . . . . . . . . . . . 84 4.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.10 Study projects . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.11 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5 HOMOMORPHISMS 95 5.1 Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . 95 5.2 Normal subgroups . . . . . . . . . . . . . . . . . . . . . . . 98 5.3 Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.4 The First Isomorphism Theorem for Groups . . . . . . . . 104 5.5 The Law of Exponents . . . . . . . . . . . . . . . . . . . . 106 5.6 Cayley’s Theorem . . . . . . . . . . . . . . . . . . . . . . . 109 5.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.8 Study projects . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.9 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6 RINGS 127 6.1 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 6.2 Distributivity . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.3 Subrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.4 Ring homomorphisms . . . . . . . . . . . . . . . . . . . . . 135 6.5 Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.6 Quotient rings . . . . . . . . . . . . . . . . . . . . . . . . . 139 6.7 Polynomial rings . . . . . . . . . . . . . . . . . . . . . . . . 140 6.8 Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . 145 6.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6.10 Study projects . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.11 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 7 FIELDS 157 7.1 Integral domains . . . . . . . . . . . . . . . . . . . . . . . . 157 7.2 Degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 7.3 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 7.4 Polynomials over fields . . . . . . . . . . . . . . . . . . . . 164 7.5 Principal ideal domains . . . . . . . . . . . . . . . . . . . . 167 7.6 Irreducible polynomials . . . . . . . . . . . . . . . . . . . . 170 7.7 Lagrange interpolation . . . . . . . . . . . . . . . . . . . . 173 vii 7.8 Fields of fractions . . . . . . . . . . . . . . . . . . . . . . . 175 7.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 7.10 Study projects . . . . . . . . . . . . . . . . . . . . . . . . . 182 7.11 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 8 FACTORIZATION 185 8.1 Factorization in integral domains . . . . . . . . . . . . . . . 185 8.2 Noetherian domains . . . . . . . . . . . . . . . . . . . . . . 188 8.3 Unique factorization domains . . . . . . . . . . . . . . . . . 190 8.4 Roots of polynomials . . . . . . . . . . . . . . . . . . . . . 193 8.5 Splitting fields . . . . . . . . . . . . . . . . . . . . . . . . . 196 8.6 Uniqueness of splitting fields . . . . . . . . . . . . . . . . . 198 8.7 Structure of finite fields . . . . . . . . . . . . . . . . . . . . 202 8.8 Galois fields . . . . . . . . . . . . . . . . . . . . . . . . . . 204 8.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 8.10 Study projects . . . . . . . . . . . . . . . . . . . . . . . . . 210 8.11 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 9 MODULES 215 9.1 Endomorphisms . . . . . . . . . . . . . . . . . . . . . . . . 215 9.2 Representing a ring . . . . . . . . . . . . . . . . . . . . . . 219 9.3 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 9.4 Submodules . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 9.5 Direct sums . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 9.6 Free modules . . . . . . . . . . . . . . . . . . . . . . . . . . 231 9.7 Vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 235 9.8 Abelian groups . . . . . . . . . . . . . . . . . . . . . . . . . 240 9.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 9.10 Study projects . . . . . . . . . . . . . . . . . . . . . . . . . 248 9.11 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 10 GROUP ACTIONS 253 10.1 Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 10.2 Orbits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 10.3 Transitive actions . . . . . . . . . . . . . . . . . . . . . . . 258 10.4 Fixed points . . . . . . . . . . . . . . . . . . . . . . . . . . 262 10.5 Faithful actions . . . . . . . . . . . . . . . . . . . . . . . . . 265 10.6 Cores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 10.7 Alternating groups . . . . . . . . . . . . . . . . . . . . . . . 270 10.8 Sylow Theorems . . . . . . . . . . . . . . . . . . . . . . . . 273 10.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 10.10 Study projects . . . . . . . . . . . . . . . . . . . . . . . . . 283 10.11 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 viii 11 QUASIGROUPS 287 11.1 Quasigroups . . . . . . . . . . . . . . . . . . . . . . . . . . 287 11.2 Latin squares . . . . . . . . . . . . . . . . . . . . . . . . . . 289 11.3 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 11.4 Quasigroup homomorphisms . . . . . . . . . . . . . . . . . 297 11.5 Quasigroup homotopies . . . . . . . . . . . . . . . . . . . . 301 11.6 Principal isotopy . . . . . . . . . . . . . . . . . . . . . . . . 304 11.7 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 11.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 11.9 Study projects . . . . . . . . . . . . . . . . . . . . . . . . . 315 11.10 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 Index 319 Preface This book is designed as an introduction to “abstract” algebra, particularly for students who have already seen a little calculus, as well as vectors and matrices in 2 or 3 dimensions. The emphasis is not placed on abstraction for its own sake, or on the axiomatic method. Rather, the intention is to present algebra as the main tool underlying discrete mathematics and the digital world, much as calculus was accepted as the main tool for continuous mathematics and the analog world. Traditionally, treatments of algebra at this level have faced a dilemma: groups first or rings first? Presenting rings first immediately offers familiar concepts such as polynomials, and builds on intuition gained from working with the integers. On the other hand, the axioms for groups are less complex than the axioms for rings. Moreover, group techniques, such as quotients by normal subgroups, underlie ring techniques such as quotients by ideals. The dilemma is resolved by emphasizing semigroups and monoids along with groups. Semigroups and monoids are steps up to groups, while rings have both a group structure and a semigroup or monoid structure. The first three chapters work at the concrete level: numbers, functions, and equivalence. Semigroups of functions and groups of permutations appear early. Functional composition, cycle notation for permutations, and matrix notation for linear functions provide techniques for practical computation, avoiding less direct methods such as generators and relations or table look- up. Equivalencerelationsareusedtointroducerationalnumbersandmodular arithmetic. TheyalsoenabletheFirstIsomorphismTheoremtobepresented at the set level, without the requirement for any group structure. If time is short (say just one quarter), the first three chapters alone may be used as a quick introduction to algebra, sufficient to exhibit irrational numbers or to gain a taste of cryptography. Abstract groups and monoids are presented in the fourth chapter. The examples include orthogonal groups and stochastic matrices, while concepts suchasLagrange’sTheoremandgroupsofunitsofmonoidsarecovered. The fifth chapter then deals with homomorphisms, leading to Cayley’s Theorem reducing abstract groups to concrete groups of permutations. Rings form the topic of the sixth chapter, while integral domains and fields follow in the seventh. The first six or seven chapters provide basic coverage of abstract algebra, suitable for a one-semester or two-quarter course. Subsequent chapters deal with slightly more advanced topics, suitable for a second semester or third quarter. Chapter 8 delves deeper into the theory ix