Undergraduate Texts in Mathematics Editors S. Axler F.W. Gehring K.A. Ribet Undergraduate Texts in Mathematics Abbott: Understanding Analysis. Childs: A Concrete Introduction to Anglin: Mathematics; A Concisc History Higher Algebra, Second edition. and Philosophy. Chung/A tSahlia: Elementary Probability Readings in Mathematics. Theory: With Stochastic Processes und Anglin/Lambck: The Heritage of an Introduction to Mathematical Thales. Finance. Fourth edition. Readings in Mathematics, Cox/Little/O'Shea: Ideals, Varieties. Apostol: Introduction to Analytic and Algorithms, Second edition. Number Theory. Second edition, Croom: Basic Concepts of Algebraic Armstrong: Basic Topology, Topology. Armstrong: Groups and Symmetry. Curtis: Linear Algebra: An Introductory Axler: Linear Algebra Done Right. Approach, Fourth edition, Second edition. Daepp/Corkin: Reading, Writing, and Beardon: Limits: A New Approach to Proving: A Closer Look at Real Analysis. Mathematics. Bak/Newman: Complex Analysis. Devlin; The Joy of Sets: Fundamentals Second edition. of Contemporary Set Theory, Banchoff/Vermer: Linear Algebra Second edition, Through Geometry. Second edition. Dixmier: General Topology. Berberian: A First Course in Real Driver: Why Math? Analysis. Ebbinghaus/Flum/Thomas: Bix: Conies and Cubics; A Mathematical Logic. Second edition. Concrete Introduction to Algebraic Edgar: Measure, Topology, and Fractal Curves. Geometry. Bremaud: An Introduction to Elaydi: An Introduction to Difference Probabilistic Modeling. Equations. Second edition, Bressoud: Factorization and Primality Erd6s/Suranyi: Topics in the Theory of Testing. Numbers. Bressoud: Second Year Calculus. Estep: Practical Analysis in One Variable. Readings in Mathematics Exner: An Accompaniment to Higher Brickmam Mathematical Introduction Mathematics. to Linear Programming and Game Exner: Inside Calculus. Theory. Fine/Rosenberger: The Fundamental Browder: Mathematical Analysis: Theory of Algebra, An Introduction. Fischer: Intermediate Real Analysis. Bucbmann: Introduction to Flanigan/Kazdan: Calculus Two: Linear Cryptography. and Nonlinear Functions. Second Buskes/van Rooij: Topological Spaces: edition. From Distance to Neighborhood. Fleming: Functions of Several Variables, Caliahan: The Geometry of Spacetimc: Second edition. An Introduction to Special and General Foulds: Combinatorial Optimization for Rclavitity. Undergraduates. Carter/van Brunt: The Lebesgue- Foulds: Optimization Techniques: An Stieltjes Integral; A Practical Introduction. Introduction Cederbcrg: A Course in Modem (continued after index) Geomelrics. Second edition. Ronald S. Irving Integers, Polynomials, and Rings A Course in Algebra Ronald S. Irving College of" Arts and Sciences University of Washington Seattle, WA 98195 USA Editorial Board S. Axler F.W. Gehring K.A. Ribet Mathematics Department Mathematics Department Mathematics Department .San Francisco State East Hall University of California, University University of Michigan Berkeley San Francisco, CA 94132 Ann Arbor, Ml 48109 Berkeley, CA 94720-3641) USA USA USA [email protected] [email protected] [email protected] Mathematics Subject Classification (2000); 12-01. 13-01 Library of Congress Cataloging-in-Publication data lrving. Ronalds., 1952- Intcgeis, polynomials, and rings : a course in algebra / Ronald S. Irving. p. cm. — (Undergraduate texts in mathematics) Includes bibliographical references and index. ISBN 0-387-40397-3 (hard cover : acid-free paper) - ISBN 0-387-20172-6 (softcover ; acid-free paper) 1. Algebra. Abstract, [.Title. II. Series, QA162.158 2003 512-dc22 2003059135 ISBN 0-387-40397-3 (hardcover] Printed on acid-free paper. ISBN 0-187-20172-6 (softcover) © 2004 Springer-Vcrlag New York. Inc. All rights reserved. This work may not lie translated or copied in whole or in part without the written permission "I the publisher [Springer-Verlag New York, Inc., 175 Fifth Avenue, New York, NY l0010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information stor- age and retrieval, eletronice trunk, adaptation, computer software, or by similar or dissimi- lar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as 1111 expression of opinion as to whether or not they are subject to proprietary rights. Printed in the United Stales of America. 987654321 SPIN 10792243 (hardcover) SPIN 10947241 (sollcover) Spritiger-Verlae is a pan of .Springer Science+Business Media springeronline.com For Gail This page intentionally left blank Preface This book began life as a set of notes that I developed for a course at the University of Washington entitled Introduction to Modern Algebra for Teach- ers. Originally conceived as a text for future secondary-school mathematics teachers,ithasdevelopedintoabookthatcouldservewellasatextinanun- dergraduatecourseinabstractalgebraoracoursedesignedasanintroduction to higher mathematics. This book differs from many undergraduate algebra texts in fundamental ways; the reasons lie in the book’s origin and the goals I set for the course. The course is a two-quarter sequence required of students intending to ful- fill the requirements of the teacher preparation option for our B.A. degree in mathematics, or of the teacher preparation minor. It is required as well of those intending to matriculate in our university’s Master’s in Teaching pro- gram for secondary mathematics teachers. This is the principal course they take involving abstraction and proof, and they come to it with perhaps as little background as a year of calculus and a quarter of linear algebra. The mathematicalabilityofthestudentsvarieswidely,asdoestheirlevelofmath- ematical interest. With such an audience, I have chosen to focus less on content and more on the doing of mathematics. Content matters, of course, but as much as a vehicle for mathematical insight as an end in itself. I wish for students to leave the course with an in-depth experience, perhaps their only one, in reading mathematics, speaking about mathematics, listening to others speak aboutmathematics,andwritingmathematics.Surely,wehopethatsecondary mathematicsteachersdeveloptheseskillsintheirownstudents;Iwanttoen- sure that they have the opportunity themselves. The course content becomes the raw material through which the students develop the ability to under- stand and communicate mathematics. I love algebra. I want my students to love algebra. But I also want them to master such skills as learning what a mathematical statement is, what a mathematical argument or proof is, how to present an argument orally, how to present an argument in writing, how viii Preface to recognize a correct proof written or spoken by someone else, and how to converse effectively about mathematics. In order to help my students achieve these goals, I strive to keep my lec- turing to a minimum, and this has forced me to write notes that students can rely on as the primary source of the mathematical material. I expect my students to learn in large measure by reading the material in the book, work- ing on the exercises, and, in groups of four or five students, discussing their findings with their colleagues. Through a combination of group discussion, individualattemptsatdiscoveringandwritingsolutions,furtherreading,and discussionswithmeandthecourseteachingassistant,thestudentsultimately master—to a greater or lesser extent—the material. Their understanding is expressed through their written proofs and oral explanations. Learning by working in groups is natural in this course for two reasons. First, the intellectual processes of proof and mathematical communication are best learned by practice; no one practices when I lecture. Second, the course is part of the students’ preparation to become mathematics teachers; as teachers, they will communicate mathematical ideas to others and listen as others do the same to them. By practicing in class, the students gain an appreciation of the difficulty and the importance of expressing mathematical ideas effectively. Animportantfacetofthecourseiswriting.Iinsistthatthestudentswrite their arguments in well-structured English prose. The teaching assistant and I provide detailed comments to help them learn how to do this. Some of the students are good writers, but they may not have realized previously that they can apply their writing skills to mathematics. For this approach to work, the material has to be handed to the students inmanageableportions,withsmallgapsbetweentheportionsforthestudent to fill in by doing the exercises, which, in turn, are themselves structured as sequences of questions with even smaller gaps between them. Whenever textbooks that I have used, or my own written materials, leave too large a gap,thestudentsfallintotheresultingchasm.Forlearningtooccur,thesteps mustbetherightsize.Thestepstakenbystandardundergraduatetextsmay suit other audiences (though not as many, in my experience, as one might suppose), but they are too large for this one, as I discovered when I first taught the course in the fall of 1996. Within a month, I began to supplement thechosentextwithcommentarythatattemptedtofillgapsincertainproofs. Then I began to write my own assignments, interweaving my material with passages in the text. Ultimately, I left the text behind, writing and rewriting assignments repeatedly as I taught the course until they evolved into this book. One nonstandard feature of the book is that I prove only a few of the the- orems in full. Most proofs are left as exercises, and these exercises form the heartofthecourse.Sometimes,thetreatmentofasingleresultisstretchedout overseveralpages,asIaskthestudenttoproveitinasequenceofcases,build- inguptothegeneralcase.AnexampleofthisisthetreatmentofEisenstein’s Preface ix criterion in Section 11.3. Almost every exercise in which a student is asked to prove a theorem contains a detailed hint or outline of the proof. Indeed, to a mathematically experienced reader, some of my outlines may appear to be complete proofs themselves. Yet, for almost all students, the outlines are far from complete. Unwinding their meaning can be a significant challenge, and the unwinding process serves as the catalyst for learning. Students try to understand what is written; discuss their understandings with each other, the teaching assistant, and me; write drafts of proofs; use class time to show thedraftstoeachotherandus;turnintheproofs;receivecomments;andtry again. I have found that the material in this book consistently challenges all the students in the course. The few students at the top of each class ultimately succeedinmeetingthechallenge,whilethelargemajorityofstudentscomplete the course with some gaps in understanding. They all leave with a much firmer appreciation of the mathematical enterprise. A few students may fall by the wayside. Perhaps this is just as well. Not everyone is intended to be a secondary mathematics teacher, and if this course provides a few with the opportunity to discover this, it has served a useful purpose. As for the content of the course, the book has three parts: “Integers,” “Polynomials,”and“AllTogetherNow.”InPartI,somefundamentalideasof algebra are introduced in the concrete context of integers, with rings brought in only in Chapter 6 as a way of organizing some of the ideas. The high point ofPartIisChapter7,inwhichFermat’sandEuler’stheoremsoncongruence are proved and RSA encryption is discussed. Part II treats polynomials with coefficients chosen from the integers or various fields. Again, the treatment is concrete at first, but ultimately makes contact with abstract ideas of ring theory. In Part III, the parallels we have seen between rings of integers and rings of polynomials are placed in the broader setting of Euclidean rings, for which some general theorems are proved and applied to the ring of Gaussian integers. The irreducible Gaussian integers are determined, and simultane- ously we determine, as Fermat first did, which prime numbers are sums of two integer squares. The choice of content—rings of integers and rings of polynomials—is a natural one for a course intended for future secondary teachers, who will go on to teach these topics in some form themselves. In the course, the topics are studied more deeply and more abstractly than at the high-school level, especiallywiththeintroductionofringsandfields.Thisprovidesthestudents with the opportunity to acquire a more advanced viewpoint on material that is at the core of secondary mathematics. The material can work equally well for a much wider range of mathematics students, and may be well suited for self-study. An important theme in the book is a familiar one in undergrad- uate algebra courses: Ideas introduced initially for the ring of integers make sense as well for rings of polynomials over fields and more generally still for Euclideanrings.Thereaderistakenthroughthesesettings,thenreturnsfrom the abstraction of Euclidean rings to the concrete example of the Gaussian