Abstract Algebra Theory And Applications
Abstract AlgebraTheory and ApplicationsThomas W. JudsonStephen F. Austin State UniversityAugust 11, 2012
iiCopyright 1997 by Thomas W. Judson.Permission is granted to copy, distribute and/or modify this document underthe terms of the GNU Free Documentation License, Version 1.2 or any laterversion published by the Free Software Foundation; with no Invariant Sections,no Front-Cover Texts, and no Back-Cover Texts. A copy of the license isincluded in the appendix entitled “GNU Free Documentation License”.A current version can always be found via abstract.pugetsound.edu.
PrefaceThis text is intended for a one- or two-semester undergraduate course inabstract algebra. Traditionally, these courses have covered the theoreticalaspects of groups, rings, and fields. However, with the development ofcomputing in the last several decades, applications that involve abstractalgebra and discrete mathematics have become increasingly important, andmany science, engineering, and computer science students are now electingto minor in mathematics. Though theory still occupies a central role in thesubject of abstract algebra and no student should go through such a coursewithout a good notion of what a proof is, the importance of applicationssuch as coding theory and cryptography has grown significantly.Until recently most abstract algebra texts included few if any applications.However, one of the major problems in teaching an abstract algebra courseis that for many students it is their first encounter with an environment thatrequires them to do rigorous proofs. Such students often find it hard to seethe use of learning to prove theorems and propositions; applied exampleshelp the instructor provide motivation.This text contains more material than can possibly be covered in a singlesemester. Certainly there is adequate material for a two-semester course, andperhaps more; however, for a one-semester course it would be quite easy toomit selected chapters and still have a useful text. The order of presentationof topics is standard: groups, then rings, and finally fields. Emphasis can beplaced either on theory or on applications. A typical one-semester coursemight cover groups and rings while briefly touching on field theory, usingChapters 1 through 6, 9, 10, 11, 13 (the first part), 16, 17, 18 (the firstpart), 20, and 21. Parts of these chapters could be deleted and applicationssubstituted according to the interests of the students and the instructor. Atwo-semester course emphasizing theory might cover Chapters 1 through 6,9, 10, 11, 13 through 18, 20, 21, 22 (the first part), and 23. On the otheriii
ivPREFACEhand, if applications are to be emphasized, the course might cover Chapters1 through 14, and 16 through 22. In an applied course, some of the moretheoretical results could be assumed or omitted. A chapter dependency chartappears below. (A broken line indicates a partial dependency.)Chapters 1–6Chapter 8Chapter 9Chapter 7Chapter 10Chapter 11Chapter 13Chapter 16Chapter 12Chapter 17Chapter 18Chapter 20Chapter 14Chapter 15Chapter 19Chapter 21Chapter 22Chapter 23Though there are no specific prerequisites for a course in abstract algebra,students who have had other higher-level courses in mathematics will generallybe more prepared than those who have not, because they will possess a bitmore mathematical sophistication. Occasionally, we shall assume some basiclinear algebra; that is, we shall take for granted an elementary knowledgeof matrices and determinants. This should present no great problem, sincemost students taking a course in abstract algebra have been introduced tomatrices and determinants elsewhere in their career, if they have not alreadytaken a sophomore- or junior-level course in linear algebra.
PREFACEvExercise sections are the heart of any mathematics text. An exercise setappears at the end of each chapter. The nature of the exercises ranges overseveral categories; computational, conceptual, and theoretical problems areincluded. A section presenting hints and solutions to many of the exercisesappears 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 indifficulty from very easy to very challenging. Many of the more substantialproblems require careful thought, so the student should not be discouragedif the solution is not forthcoming after a few minutes of work.There are additional exercises or computer projects at the ends of manyof the chapters. The computer projects usually require a knowledge ofprogramming. All of these exercises and projects are more substantial innature 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 abstractalgebra. Comprehensive discussion about Sage, and a selection of relevantexercises, are provided in an electronic format that may be used with theSage Notebook in a web browser, either on your own computer, or at a publicserver such as sagenb.org. Look for this supplement at the book’s website:abstract.pugetsound.edu. In printed versions of the book, we include abrief description of Sage’s capabilities at the end of each chapter, right afterthe references.The open source version of this book has received support from theNational Science Foundation (Award # 1020957).AcknowledgementsI would like to acknowledge the following reviewers for their helpful commentsand suggestions. David Anderson, University of Tennessee, Knoxville Robert Beezer, University of Puget Sound Myron Hood, California Polytechnic State University Herbert Kasube, Bradley University John Kurtzke, University of Portland Inessa Levi, University of Louisville
viPREFACE Geoffrey Mason, University of California, Santa Cruz Bruce Mericle, Mankato State University Kimmo Rosenthal, Union College Mark Teply, University of WisconsinI would also like to thank Steve Quigley, Marnie Pommett, Cathie Griffin,Kelle Karshick, and the rest of the staff at PWS for their guidance throughoutthis project. It has been a pleasure to work with them.Thomas W. Judson
ContentsPrefaceiii1 Preliminaries1.1 A Short Note on Proofs . . . . . . . . . . . . . . . . . . . . .1.2 Sets and Equivalence Relations . . . . . . . . . . . . . . . . .1142 The Integers232.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . 232.2 The Division Algorithm . . . . . . . . . . . . . . . . . . . . . 273 Groups373.1 Integer Equivalence Classes and Symmetries . . . . . . . . . . 373.2 Definitions and Examples . . . . . . . . . . . . . . . . . . . . 423.3 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 Cyclic Groups594.1 Cyclic Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . 594.2 Multiplicative Group of Complex Numbers . . . . . . . . . . 634.3 The Method of Repeated Squares . . . . . . . . . . . . . . . . 685 Permutation Groups765.1 Definitions and Notation . . . . . . . . . . . . . . . . . . . . . 775.2 Dihedral Groups . . . . . . . . . . . . . . . . . . . . . . . . . 856 Cosets and Lagrange’s Theorem946.1 Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 946.2 Lagrange’s Theorem . . . . . . . . . . . . . . . . . . . . . . . 976.3 Fermat’s and Euler’s Theorems . . . . . . . . . . . . . . . . . 99vii
viiiCONTENTS7 Introduction to Cryptography1037.1 Private Key Cryptography . . . . . . . . . . . . . . . . . . . . 1047.2 Public Key Cryptography . . . . . . . . . . . . . . . . . . . . 1078 Algebraic Coding Theory8.1 Error-Detecting and Correcting Codes8.2 Linear Codes . . . . . . . . . . . . . .8.3 Parity-Check and Generator Matrices8.4 Efficient Decoding . . . . . . . . . . .1151151241281359 Isomorphisms1449.1 Definition and Examples . . . . . . . . . . . . . . . . . . . . . 1449.2 Direct Products . . . . . . . . . . . . . . . . . . . . . . . . . . 14910 Normal Subgroups and Factor Groups15910.1 Factor Groups and Normal Subgroups . . . . . . . . . . . . . 15910.2 The Simplicity of the Alternating Group . . . . . . . . . . . . 16211 Homomorphisms16911.1 Group Homomorphisms . . . . . . . . . . . . . . . . . . . . . 16911.2 The Isomorphism Theorems . . . . . . . . . . . . . . . . . . . 17212 Matrix Groups and Symmetry17912.1 Matrix Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 17912.2 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18813 The Structure of Groups20013.1 Finite Abelian Groups . . . . . . . . . . . . . . . . . . . . . . 20013.2 Solvable Groups . . . . . . . . . . . . . . . . . . . . . . . . . 20514 Group Actions14.1 Groups Acting on Sets . . . . . . . . . . . . . . . . . . . . . .14.2 The Class Equation . . . . . . . . . . . . . . . . . . . . . . .14.3 Burnside’s Counting Theorem . . . . . . . . . . . . . . . . . .21321321721915 The Sylow Theorems23115.1 The Sylow Theorems . . . . . . . . . . . . . . . . . . . . . . . 23115.2 Examples and Applications . . . . . . . . . . . . . . . . . . . 235
CONTENTS16 Rings16.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 Designix.24324324825025425717 Polynomials17.1 Polynomial Rings . . . . . . . . . . . . . . . . . . . . . . . . .17.2 The Division Algorithm . . . . . . . . . . . . . . . . . . . . .17.3 Irreducible Polynomials . . . . . . . . . . . . . . . . . . . . .268269273277.18 Integral Domains28818.1 Fields of Fractions . . . . . . . . . . . . . . . . . . . . . . . . 28818.2 Factorization in Integral Domains . . . . . . . . . . . . . . . . 29219 Lattices and Boolean Algebras19.1 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19.2 Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . .19.3 The Algebra of Electrical Circuits . . . . . . . . . . . . . . . .30630631131720 Vector Spaces32420.1 Definitions and Examples . . . . . . . . . . . . . . . . . . . . 32420.2 Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32620.3 Linear Independence . . . . . . . . . . . . . . . . . . . . . . . 32721 Fields21.1 Extension Fields . . . . . . . . . . . . . . . . . . . . . . . . .21.2 Splitting Fields . . . . . . . . . . . . . . . . . . . . . . . . . .21.3 Geometric Constructions . . . . . . . . . . . . . . . . . . . . .33433434534822 Finite Fields35822.1 Structure of a Finite Field . . . . . . . . . . . . . . . . . . . . 35822.2 Polynomial Codes . . . . . . . . . . . . . . . . . . . . . . . . 36323 Galois Theory37623.1 Field Automorphisms . . . . . . . . . . . . . . . . . . . . . . 37623.2 The Fundamental Theorem . . . . . . . . . . . . . . . . . . . 38223.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390Hints and Solutions399
xCONTENTSGNU Free Documentation License414Notation422Index426
1PreliminariesA certain amount of mathematical maturity is necessary to find and studyapplications of abstract algebra. A basic knowledge of set theory, mathematical induction, equivalence relations, and matrices is a must. Even moreimportant is the ability to read and understand mathematical proofs. Inthis chapter we will outline the background needed for a course in abstractalgebra.1.1A Short Note on ProofsAbstract mathematics is different from other sciences. In laboratory sciencessuch as chemistry and physics, scientists perform experiments to discovernew principles and verify theories. Although mathematics is often motivatedby physical experimentation or by computer simulations, it is made rigorousthrough the use of logical arguments. In studying abstract mathematics, wetake what is called an axiomatic approach; that is, we take a collection ofobjects S and assume some rules about their structure. These rules are calledaxioms. Using the axioms for S, we wish to derive other information aboutS by using logical arguments. We require that our axioms be consistent; thatis, they should not contradict one another. We also demand that there notbe too many axioms. If a system of axioms is too restrictive, there will befew examples of the mathematical structure.A statement in logic or mathematics is an assertion that is either trueor false. Consider the following examples: 3 56 13 8/2. All cats are black. 2 3 5.1
2CHAPTER 1PRELIMINARIES 2x 6 exactly when x 4. If ax2 bx c 0 and a 6 0, then b b2 4acx .2a x3 4x2 5x 6.All but the first and last examples are statements, and must be either trueor false.A mathematical proof is nothing more than a convincing argumentabout the accuracy of a statement. Such an argument should contain enoughdetail 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 that6 6 8, an argument that would satisfy anyone. Of course, audiences mayvary widely: proofs can be addressed to another student, to a professor, orto 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 toomuch detail is omitted, then the proof may not be convincing. Again itis important to keep the audience in mind. High school students requiremuch more detail than do graduate students. A good rule of thumb for anargument in an introductory abstract algebra course is that it should bewritten to convince one’s peers, whether those peers be other students orother readers of the text.Let us examine different types of statements. A statement could be assimple as “10/5 2”; however, mathematicians are usually interested inmore complex statements such as “If p, then q,” where p and q are bothstatements. If certain statements are known or assumed to be true, wewish to know what we can say about other statements. Here p is calledthe hypothesis and q is known as the conclusion. Consider the followingstatement: If ax2 bx c 0 and a 6 0, then b b2 4acx .2aThe hypothesis is ax2 bx c 0 and a 6 0; the conclusion is b b2 4acx .2aNotice that the statement says nothing about whether or not the hypothesisis true. However, if this entire statement is true and we can show that
1.1A SHORT NOTE ON PROOFS3ax2 bx c 0 with a 6 0 is true, then the conclusion must be true. Aproof of this statement might simply be a series of equations:ax2 bx c 0bcx2 x aa 2 2bbbcx2 x a2a2aa 22bb 4acx 2a4a2 b2 4acb x 2a2a b b2 4acx .2aIf we can prove a statement true, then that statement is called a proposition. A proposition of major importance is called a theorem. Sometimesinstead of proving a theorem or proposition all at once, we break the proofdown into modules; that is, we prove several supporting propositions, whichare called lemmas, and use the results of these propositions to prove themain result. If we can prove a proposition or a theorem, we will often,with very little effort, be able to derive other related propositions calledcorollaries.Some Cautions and SuggestionsThere are several different strategies for proving propositions. In addition tousing different methods of proof, students often make some common mistakeswhen they are first learning how to prove theorems. To aid students whoare studying abstract mathematics for the first time, we list here some ofthe difficulties that they may encounter and some of the strategies of proofavailable to them. It is a good idea to keep referring back to this list as areminder. (Other techniques of proof will become apparent throughout thischapter and the remainder of the text.) A theorem cannot be proved by example; however, the standard way toshow that a statement is not a theorem is to provide a counterexample. Quantifiers are important. Words and phrases such as only, for all, forevery, and for some possess different meanings.
4CHAPTER 1PRELIMINARIES 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. Firstshow 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 showthat r s. Sometimes it is easier to prove the contrapositive of a statement.Proving the statement “If p, then q” is exactly the same as proving thestatement “If not q, then not p.” Although it is usually better to find a direct proof of a theorem, thistask can sometimes be difficult. It may be easier to assume that thetheorem that you are trying to prove is false, and to hope that in thecourse of your argument you are forced to make some statement thatcannot possibly be true.Remember that one of the main objectives of higher mathematics isproving theorems. Theorems are tools that make new and productive applications of mathematics possible. We use examples to give insight intoexisting theorems and to foster intuitions as to what new theorems might betrue. Applications, examples, and proofs are tightly interconnected—muchmore so than they may seem at first appearance.1.2Sets and Equivalence RelationsSet TheoryA set is a well-defined collection of objects; that is, it is defined in sucha manner that we can determine for any given object x whether or not xbelongs to the set. The objects that belong to a set are called its elementsor members. We will denote sets by capital letters, such as A or X; if a isan element of the set A, we write a A.A set is usually specified either by listing all of its elements inside a pairof braces or by stating the property that determines whether or not an objectx belongs to the set. We might writeX {x1 , x2 , . . . , xn }for a set containing elements x1 , x2 , . . . , xn orX {x : x satisfies P}
1.2SETS AND EQUIVALENCE RELATIONS5if each x in X satisfies a certain property P. For example, if E is the set ofeven positive integers, we can describe E by writing eitherE {2, 4, 6, . . .} orE {x : x is an even integer and x 0}.We write 2 E when we want to say that 2 is in the set E, and 3 / E tosay 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 6 0};R {x : x is a real number};C {z : z is a complex number}.We find various relations between sets and can perform operations onsets. A set A is a subset of B, written A B or B A, if every element ofA is also an element of B. For example,{4, 5, 8} {2, 3, 4, 5, 6, 7, 8, 9}andN Z Q R C.Trivially, every set is a subset of itself. A set B is a proper subset of aset A if B A but B 6 A. If A is not a subset of B, we write A 6 B; forexample, {4, 7, 9} 6 {2, 4, 5, 8, 9}. Two sets are equal, written A B, if wecan show that A B and B A.It is convenient to have a set with no elements in it. This set is calledthe empty set and is denoted by . Note that the empty set is a subset ofevery 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 asA B {x : x A or x B};the intersection of A and B is defined byA B {x : x A and x B}.If A {1, 3, 5} and B {1, 2, 3, 9}, thenA B {1, 2, 3, 5, 9}and A B {1, 3}.
6CHAPTER 1PRELIMINARIESWe can consider the union and the intersection of more than two sets. Inthis case we writen[Ai A1 . . . Ani 1andn\Ai A1 . . . Ani 1for 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 ar
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
Robert Gerver, Ph.D. North Shore High School 450 Glen Cove Avenue Glen Head, NY 11545 gerverr@northshoreschools.org Rob has been teaching at . Algebra 1 Financial Algebra Geometry Algebra 2 Algebra 1 Geometry Financial Algebra Algebra 2 Algebra 1 Geometry Algebra 2 Financial Algebra ! Concurrently with Geometry, Algebra 2, or Precalculus
So you can help us find X Teacher/Class Room Pre-Algebra C-20 Mrs. Hernandez Pre-Algebra C-14 . Kalscheur Accelerated Math C-15 Mrs. Khan Honors Algebra 2 Honors Geometry A-21 Mrs. King Math 7 Algebra 1 Honors Algebra 1 C-19 Mrs. Looft Honors Algebra C-16 Mr. Marsh Algebra 1 Honors Geometry A-24 Mrs. Powers Honors Pre-Algebra C-18 Mr. Sellaro .
McDougal Littell Algebra I 2004 McDougal Littell Algebra I: Concepts and Skills 2004 Prentice Hall Algebra I, Virginia Edition 2006 Algebra I (continued) Prentice Hall Algebra I, Virginia Edition Interactive Textbook 2006 CORD Communications, Inc. Algebra I 2004 Glencoe/McGraw Hill Algebra: Concepts and Applications, Volumes 1 and 2 2005
This course will provide a rigorous introduction to abstract algebra, including group theory and linear algebra. Topics include: 1. Set theory. Formalization of Z,Q,R,C. 2. Linear algebra. Vector spaces and transformations over Rand C. Other ground fields. Eigenvectors. Jordan form. 3. Multilinear algebra. Inner products, quadraticforms .
A Book of Abstract Algebra, 2. nd. edition, by Charles C Pinter. ISBN-13: 978-0486474175 : ISBN-10: 0486474178 . Elements of Number Theory, by John Stillwell . ISBN-13: 978-1441930668 . . Chapter 1 Why Abstract Algebra? Chapter 2 Operations A book of Abstract Algebra . Day 8 . Chapter 3 The Definition of
MATH 543- Abstract Algebra I Course Syllabus: Fall 2018 INSTRUCTOR INFORMATION Instructor: Padmapani Seneviratne, Ph.D. Phone: 903- 886-5952 . Textbook: Abstract Algebra, Dummit and Foote (3rd edition), Wiley, ISBN-10: 0471433349 . Use a computer algebra system to construct and evaluate groups. 6). Learn applications of groups and related .
High-level description of course goals: 1. linear algebra theory; 2. linear algebra computa-tional skills; 3. introduction to abstract math. Today’s topic: introduction to linear algebra. Conceptually, linear algebra is about sets of quantities (a.k.a. vectors
Title: Prentice Hall Algebra 1, Geometry, and Algebra 2 (Florida) : Program Components Author: Pearson Subject: Prentice Hall Algebra 1, Geometry, and Algebra 2 (Florida)
