Galois Group Rational Number Irrational Element Abstract Algebra Exam Practice

Instructions
1. You may use a calculator to help you with simple arithmetic (+, −, ×, /). No other computational aids are permitted.
2. You may consult the course textbook (Beachy/Blair) and your own notes, and you may ask
me for help. No other sources (online or otherwise) are permitted.
Problems
1. Let f (x) = x3 + 5×2 + 1 and let u ∈ C be a root of f (x).
(a) Show that f (x) is irreducible over Q.
(b) Express (1 + u2 )−1 in the form a + bu + cu2 for a, b, c ∈ Q.
2. (a) Suppose α ∈ C is of degree 5 over Q. Prove that K(α) = K(α3 ).
(b) Show that every irrational element of Q(π) is transcendental. (You may assume π is
transcendental.)
(c) Let a, b ∈ C. Show that if both a + b and ab are algebraic, then so are a and b.
√ √
3. Let F = Q( 2, 3 3).
(a) Calculate [F : Q] and give a basis of F over Q.
√
√
(b) Is 2 − 3 3 a primitive element for F over Q? Explain.
4. (a) Show that cos( 2π
7 ) is algebraic over Q by finding its minimal polynomial.
(Hint: α = 12 (ζ + ζ −1 ) where ζ = e2πi/7 )
(b) Show that Q(α) is a normal extension of Q.
√
(c) Is there a rational number β for which Q(α) = Q( 3 β)? Explain.
(d) Prove that a regular heptagon is not constructible by ruler and compass.
5. Construct the splitting field of f (x) = x3 + 2×2 + 1 over Z3 and explicitly list the elements of
its Galois group.
6. Let g(x) = x5 − x4 − 4x + 4.
(a) Find the splitting field F of g(x) over Q and explicitly describe G = Gal(F/Q) as a
subgroup of S5 .
(b) List all subgroups of G and the corresponding intermediate fields between Q and F .
7. The Galois group of f (x) ∈ Q[x] over Q is of order 10. Prove that f (x) is solvable by radicals.
(Hint: Z10 and D5 are the only groups of order 10.)
8. The polynomial f (x) ∈ Q[x] is irreducible and its Galois group over Q has order 9. What
can you deduce about f (x)?
(Note: This is an open-ended question. Tell me whatever you can.)
1
Abstract Algebra
Fourth Edition
John A. Beachy
William D. Blair
Northern Illinois University
WAVELAND
PRESS, INC.
Long Grove, Illinois
For information about this book, contact:
Waveland Press, Inc.
4180 IL Route 83, Suite 101
Long Grove, IL 60047-9580
(847) 634-0081
info@waveland.com
www.waveland.com
Copyright © 2019 by John A. Beachy and William D. Blair
10-digit ISBN 1-4786-3869-9
13-digit ISBN 978-1-4786-3869-8
All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or
transmitted in any form or by any means without permission in writing from the publisher.
Printed in the United States of America
7
6
5
4
3
2
1
Contents
PREFACE
vii
PREFACE TO THE THIRD EDITION
viii
PREFACE TO THE SECOND EDITION
ix
TO THE STUDENT
xiii
WRITING PROOFS
xvi
HISTORICAL BACKGROUND
xxi
1
2
3
INTEGERS
1.1 Divisors . . . . . .
1.2 Primes . . . . . . .
1.3 Congruences . . .
1.4 Integers Modulo n .
Notes . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
3
16
27
38
50
FUNCTIONS
2.1 Functions . . . . . . .
2.2 Equivalence Relations .
2.3 Permutations . . . . .
Notes . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
51
53
66
76
90
GROUPS
3.1 Definition of a Group .
3.2 Subgroups . . . . . . .
3.3 Constructing Examples
3.4 Isomorphisms . . . . .
3.5 Cyclic Groups . . . . .
3.6 Permutation Groups . .
3.7 Homomorphisms . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
91
92
108
122
132
143
150
161
.
.
.
.
.
iii
iv
CONTENTS
3.8 Cosets, Normal Subgroups, and Factor Groups . . . . . . . . . . . 173
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
4
5
6
7
8
POLYNOMIALS
4.1 Fields; Roots of Polynomials . .
4.2 Factors . . . . . . . . . . . . . .
4.3 Existence of Roots . . . . . . .
4.4 Polynomials over Z, Q, R, and C
Notes . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
189
189
202
213
221
234
COMMUTATIVE RINGS
5.1 Commutative Rings; Integral Domains
5.2 Ring Homomorphisms . . . . . . . .
5.3 Ideals and Factor Rings . . . . . . . .
5.4 Quotient Fields . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
235
236
248
262
273
280
FIELDS
6.1 Algebraic Elements . . . . . . . . . . . .
6.2 Finite and Algebraic Extensions . . . . .
6.3 Geometric Constructions . . . . . . . . .
6.4 Splitting Fields . . . . . . . . . . . . . .
6.5 Finite Fields . . . . . . . . . . . . . . . .
6.6 Irreducible Polynomials over Finite Fields
6.7 Quadratic Reciprocity . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
281
282
289
295
301
307
313
320
328
STRUCTURE OF GROUPS
7.1 Isomorphism Theorems; Automorphisms
7.2 Conjugacy . . . . . . . . . . . . . . . . .
7.3 Groups Acting on Sets . . . . . . . . . .
7.4 The Sylow Theorems . . . . . . . . . . .
7.5 Finite Abelian Groups . . . . . . . . . . .
7.6 Solvable Groups . . . . . . . . . . . . . .
7.7 Simple Groups . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
329
330
337
345
353
358
366
374
GALOIS THEORY
8.1 The Galois Group of a Polynomial . . . . . .
8.2 Multiplicity of Roots . . . . . . . . . . . . .
8.3 The Fundamental Theorem of Galois Theory
8.4 Solvability by Radicals . . . . . . . . . . . .
8.5 Cyclotomic Polynomials . . . . . . . . . . .
8.6 Computing Galois Groups . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
383
384
390
394
405
411
417
.
.
.
.
.
.
.
.
.
.
CONTENTS
9
v
UNIQUE FACTORIZATION
427
9.1 Principal Ideal Domains . . . . . . . . . . . . . . . . . . . . . . 428
9.2 Unique Factorization Domains . . . . . . . . . . . . . . . . . . . 435
9.3 Some Diophantine Equations . . . . . . . . . . . . . . . . . . . . 441
10 GROUPS: SELECTED TOPICS
10.1 Nilpotent Groups . . . . . . . . . . . .
10.2 Internal Semidirect Products of Groups
10.3 External Semidirect Products of Groups
10.4 Classification of Groups of Small Order
10.5 The Orthogonal Group O2 .R/ . . . . .
10.6 Isometries of R2 . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
453
453
457
463
471
477
481
APPENDIX
A.1 Sets . . . . . . . . . . . . . . . . . . .
A.2 Construction of the Number Systems . .
A.3 Basic Properties of the Integers . . . . .
A.4 Induction . . . . . . . . . . . . . . . .
A.5 Complex Numbers . . . . . . . . . . .
A.6 Solution of Cubic and Quartic Equations
A.7 Dimension of a Vector Space . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
487
487
490
493
495
498
504
512
BIBLIOGRAPHY
516
SELECTED ANSWERS
518
INDEX OF SYMBOLS
527
INDEX
531
PREFACE
In this edition we hope to have corrected mistakes and typographical errors in the
previous one. In the early chapters, we have added a few examples and exercises;
in Chapters 7 and 8 we have added a significant number of more difficult exercises.
We have also added new material on groups in Chapter 10, including semidirect
products and the classification of groups of order < 16. The last two sections of the chapter are devoted to applications of group theory to the geometry of the plane. On meeting a new theorem, it is important for the student to look back at the theorems on which it depends. Perhaps just as important is to have some idea as to where it might be used later in the development. To address this, to the early chapters we have added a few paragraphs titled “Looking ahead”, to put some theorems in context. We would like to point out to both students and instructors that there is some supplementary material available on the book’s website: www:mat h:ni u:edu= beachy=abst ract algebra=. This includes solutions to a few selected exercises, marked by the symbol  in the text. Many of these exercises are ones that are referred to in the text or are used in a significant way in subsequent exercises. The file Selected Solutions for Students is also available on the Waveland Press website. In addition to the books mentioned in the prefaces of earlier editions, we wish to acknowledge the influence of the books of M. Artin and A. R. Wadsworth listed in the bibliography. Finally, we would like to thank our publisher, Neil Rowe, for his continued support, and, in particular, for his encouragement to work on another edition. DeKalb, Illinois John A. Beachy William D. Blair December 1, 2018 vii viii PREFACE PREFACE TO THE THIRD EDITION This edition would probably not have been written without the impetus from George Bergman, of the University of California, Berkeley. After using the book, on more than one occasion he sent us a large number of detailed suggestions on how to improve the presentation. Many of these were in response to questions from his students, so we owe an enormous debt of gratitude to his students, as well as to Professor Bergman. We believe that our responses to his suggestions and corrections have measurably improved the book. We would also like to acknowledge important corrections and suggestions that we received from Marie Vitulli, of the University of Oregon, and from David Doster, of Choate Rosemary Hall. We have also benefited over the years from numerous comments from our own students and from a variety of colleagues. We would like to add Doug Bowman, Dave Rusin, and Jeff Thunder to the list of colleagues given in the preface to the second edition. In this edition we have added a number of exercises, we have added 1 to all rings, and we have done our best to weed out various errors and misprints. We use the book in a linear fashion, but there are some alternatives to that approach. With students who already have some acquaintance with the material in Chapters 1 and 2, it would be possible to begin with Chapter 3, on groups, using the first two chapters for a reference. We view these chapters as studying cyclic groups and permutation groups, respectively. Since Chapter 7 continues the development of group theory, it is possible to go directly from Chapter 3 to Chapter 7. Chapter 5 contains basic facts about commutative rings, and contains many examples which depend on a knowledge of polynomial rings from Chapter 4. Chapter 5 also depends on Chapter 3, since we make use of facts about groups in the development of ring theory, particularly in Section 5.3 on factor rings. After covering Chapter 5, it is possible to go directly to Chapter 9, which has more ring theory and some applications to number theory. Our development of Galois theory in Chapter 8 depends on results from Chapters 5 and 6. Section 8.4, on solvability by radicals, requires a significant amount of material from Chapter 7. Rather than outlining a large number of possible paths through various parts of the text, we have to ask the instructor to read ahead and use a great deal of caution in choosing any paths other than the ones we have suggested above. Finally, we would like to thank our publisher, Neil Rowe, for his continued support of our writing. DeKalb, Illinois John A. Beachy William D. Blair September 1, 2005 PREFACE ix PREFACE TO THE SECOND EDITION An abstract algebra course at the junior/senior level, whether for one or two semesters, has been a well-established part of the curriculum for mathematics majors for over a generation. Our book is intended for this course, and has grown directly out of our experience in teaching the course at Northern Illinois University. As a prerequisite to the abstract algebra course, our students are required to have taken a sophomore level course in linear algebra that is largely computational, although they have been introduced to proofs to some extent. Our classes include students preparing to teach high school, but almost no computer science or engineering students. We certainly do not assume that all of our students will go on to graduate school in pure mathematics. In searching for appropriate text books, we have found several texts that start at about the same level as we do, but most of these stay at that level, and they do not teach nearly as much mathematics as we desire. On the other hand, there are several fine books that start and finish at the level of our Chapters 3 through 6, but these books tend to begin immediately with the abstract notion of group (or ring), and then leave the average student at the starting gate. We have in the past used such books, supplemented by our Chapter 1. Historically the subject of abstract algebra arose from concrete problems, and it is our feeling that by beginning with such concrete problems we will be able to generate the student’s interest in the subject and at the same time build on the foundation with which the student feels comfortable. Although the book starts in a very concrete fashion, we increase the level of sophistication as the book progresses, and, by the end of Chapter 6, all of the topics taught in our course have been covered. It is our conviction that the level of sophistication should increase, slowly at first, as the students become familiar with the subject. We think our ordering of the topics speaks directly to this assertion. Recently there has been a tendency to yield to demands of “relevancy,” and to include “applications” in this course. It is our feeling that such inclusions often tend to be superficial. In order to make room for the inclusion of applications, some important mathematical concepts have to be sacrificed. It is clear that one must have substantial experience with abstract algebra before any genuine applications can be treated. For this reason we feel that the most honest introduction concentrates on the algebra. One of the reasons frequently given for treating applications is that they motivate the student. We prefer to motivate the subject with concrete problems from areas that the students have previously encountered, namely, the integers and polynomials over the real numbers. One problem with most treatments of abstract algebra, whether they begin with group theory or ring theory, is that the students simultaneously encounter for the first time both abstract mathematics and the requirement that they produce proofs x PREFACE of their own devising. By taking a more concrete approach than is usual, we hope to separate these two initiations. In three of the first four chapters of our book we discuss familiar concrete mathematics: number theory, functions and permutations, and polynomials. Although the objects of study are concrete, and most are familiar, we cover quite a few nontrivial ideas and at the same time introduce the student to the subtle ideas of mathematical proof. (At Northern Illinois University, this course and Advanced Calculus are the traditional places for students to learn how to write proofs.) After studying Chapters 1 and 2, the students have at their disposal some of the most important examples of groups—permutation groups, the group of integers modulo n, and certain matrix groups. In Chapter 3 the abstract definition of a group is introduced, and the students encounter the notion of a group armed with a variety of concrete examples. Probably the most difficult notion in elementary group theory is that of a factor group. Again this is a case where the difficulty arises because there are, in fact, two new ideas encountered together. We have tried to separate these by treating the notions of equivalence relation and partition in Chapter 2 in the context of sets and functions. We consider there the concept of factoring a function into “better” functions, and show how the notion of a partition arises in this context. These ideas are related to the integers modulo n, studied in Chapter 1. When factor groups are introduced in Chapter 3, we have partitions and equivalence relations at our disposal, and we are able to concentrate on the group structure introduced on the equivalence classes. In Chapter 4 we return to a more concrete subject when we derive some important properties of polynomials. Here we draw heavily on the students’ familiarity with polynomials from high school algebra and on the parallel between the properties of the integers studied in Chapter 1 and the polynomials. Chapter 5 then introduces the abstract definition of a ring after we have already encountered several important examples of rings: the integers, the integers modulo n, and the ring of polynomials with coefficients in any field. From this point on our book looks more like a traditional abstract algebra textbook. After rings we consider fields, and we include a discussion of root adjunction as well as the three problems from antiquity: squaring the circle, duplicating the cube, and trisecting an angle. We also discuss splitting fields and finite fields here. We feel that the first six chapters represent the most that students at institutions such as ours can reasonably absorb in a year. Chapter 7 returns to group theory to consider several more sophisticated ideas including those needed for Galois theory, which is the subject matter of Chapter 8. In Chapter 9 we return to a study of rings, and consider questions of unique factorization. As a number theoretic application, we present a proof of Fermat’s last theorem for the exponent 3. In fact, this is the last of a thread of number theoretic applications that run through the text, including a proof of the quadratic reciprocity law in Section 6.7 and a study of primitive roots modulo p in Section 7.5. The applications to number theory provide topics suitable for honors students. PREFACE xi The last three chapters are intended to make the book suitable for an honors course or for classes of especially talented or well-prepared students. In these chapters the writing style is rather terse and demanding. Proofs are included for the Sylow theorems, the structure theorem for finite abelian groups, theorems on the simplicity of the alternating group and the special linear group over a finite field, the fundamental theorem of Galois theory, Abel’s theorem on the insolvability of the quintic, and the theorem that a polynomial ring over a unique factorization domain is again a unique factorization domain. The only prerequisite for our text is a sophomore level course in linear algebra. We do not assume that the student has been required to write, or even read, proofs before taking our course. We do use examples from matrix algebra in our discussion of group theory, and we draw on the computational techniques learned in the linear algebra course—see, for example, our treatment of the Euclidean algorithm in Chapter 1. We have included a number of appendices to which the student may be referred for background material. The appendices on induction and on the complex numbers might be appropriate to cover in class, and so they include some exercises. In our classes we usually intend to cover Chapters 1, 2, 3 in the first semester, and most of Chapters 4, 5 and 6 in the second semester. In practice, we usually begin the second semester with group homomorphisms and factor groups, and end with geometric constructions. We have rarely had time to cover splitting fields and finite fields. For students with better preparation, Chapters 1 and 2 could be covered more quickly. The development is arranged so that Chapter 7 on the structure of groups can be covered immediately after Chapter 3. On the other hand, the material from Chapter 7 is not really needed until Section 8.4, at which point we need results on solvable groups. We have included answers to some of the odd numbered computational exercises. In the exercise sets, the problems for which answers are given in the answer key are marked by the symbol Ž. ACKNOWLEDGMENTS To list all of the many sources from which we have learned is almost impossible. Perhaps because we are ring theorists ourselves, we have been attracted to and influenced by the work of two ring theorists—I. N. Herstein in Topics in Algebra and N. Jacobson in Basic Algebra I, II. In most cases our conventions, notation, and symbols are consistent with those used by Jacobson. We certainly need to mention the legacy of E. Noether, which we have met via the classic text Algebra by B. L. van der Waerden. Our treatment of Galois theory is influenced by the writing of E. Artin. In many ways our approach to abstract concepts via concrete examples is similar in flavor to that of Birkhoff and Mac Lane in A Survey of Modern Algebra, although we have chosen to take a naive approach to the development of the number systems and have omitted any discussion of ordered fields. We have also been xii PREFACE influenced by the historical approaches and choice of material in Abstract Algebra: A First Course by L. Goldstein and Introduction to Abstract Algebra by L. Shapiro. Many colleagues have taught from preliminary versions of parts of this book. We would like to thank a number of them for their comments: Harvey Blau, Harald Ellers, John Ewell, Tac Kambayashi, Henry Leonard, John Lindsey, Martin Lorenz, Donald McAlister, Robert McFadden, Gunnar Sigurdsson, George Seelinger, Doug Weakley, and John Wolfskill. Various students have offered comments and pointed out errors. We are particularly indebted to Svetlana Butler, Penny Fuller, Lauren Grubb, Michelle Mace, and Susan Talarico for giving us lists of misprints. We would like to thank all of the reviewers of our previous version, including: Victor Camillo, The University of Iowa; John C. Higgins, Brigham Young University; I. Martin Isaacs, University of Wisconsin, Madison; Paul G. Kumpel, State University of New York at Stony Brook; and Mark L. Teply, University of Wisconsin, Milwaukee. We would also like to thank Neil Rowe of Waveland Press for keeping our book in print at a reasonable price. This seems to be an appropriate place to record our thanks to Goro Azumaya and Lance Small (respectively) for their inspiration, influence, and contributions to our mathematical development. Finally, we would like to thank our families: Marcia, Gwendolyn, Elizabeth, and Hannah Beachy and Kathy, Carla, and Stephanie Blair. John A. Beachy William D. Blair 1995 TO THE STUDENT xiii TO THE STUDENT This book has grown out of our experiences in teaching abstract algebra over a considerable period of time. Our students have generally had three semesters of calculus, followed by a semester of linear algebra, and so we assume only this much background. This has meant that our students have had some familiarity with the abstract concepts of vector spaces and linear transformations. They have even had to write out a few short proofs in previous courses. But they have not usually been prepared for the depth in our course, where we require that almost everything be proved quite carefully. Learning to write proofs has always been a major stumbling block. The best advice we can give in this regard is to urge you to talk to your teacher. Each ten minutes of help in the early going will save hours later. Don’t be discouraged if you can’t solve all of the exercises. Do the ones you are assigned, try lots of others, and come back to the ones you can’t do on the first try. From time to time there will be “misplaced” exercises. By this we mean exercises for which you have sufficient tools to solve the problem as it appears, but which have easier solutions after better techniques have been introduced at a later stage. Simply attempting one of these problems (even if the attempt ends in failure) can help you understand certain ideas when they are introduced later. For this reason we urge you to keep coming back to exercises that you cannot solve on the first try. We urge any student who feels in need of a pep talk to reread this part of the preface. The same general comment applies to the introductions to each chapter, and to the notes at the ends of chapters. When first read, these introductory comments are meant to motivate the material that follows by indicating why it is interesting or important and at the same time relating this new material to things from the student’s background. They are also intended to tie together various concepts to be introduced in the chapter, and so some parts will make more sense after the relevant part of the chapter has been covered in detail. Not only will the introductions themselves make more sense on rereading, but the way in which they tie the subject matter of the chapter into the broader picture should be easier to understand. We often hear comments or questions similar to the ones we have listed below. We hope that our responses will be helpful to you as you begin studying our book. “I have to read the text several times before I begin to understand it.” Yes, you should probably expect to have to do this. In fact, you might benefit from a “slow reading” rather than a “speed reading” course. There aren’t many pages in a section, so you can afford to read them line by line. You should make sure that you can supply any reasons that may have been left out. We have written the book with the intention of gradually raising the level as it progresses. That simply means that we take more for granted, that we leave out more details. We xiv TO THE STUDENT hope to force you to become more sophisticated as you go along, so that you can supply more and more of the details on your own. “I understand the definitions and theorems, but I can’t do the problems.” Please forgive us for being skeptical of this statement. Often it just simply isn’t the case. How do you really understand a definition or a theorem? Being able to write down a definition constitutes the first step. But to put it into context you need a good variety of examples, which should allow you to relate a new definition to facts you already know. As with any mathematical subject, there is a symbiotic duality between its theorems and examples. On the one hand, theorems organize a collection of examples, while on the other hand, examples illustrate the theorems. Without interesting examples, the theory would be vacuous, and without a coherent theory, the collection of examples would be chaotic. With each definition you should associate several examples, simple enough to understand thoroughly, but complex enough to illustrate the properties inherent in the definition. In writing the book we have tried to provide good examples for each definition, but you may need to come up with your own examples based on your particular background and interests. Understanding a proof is similar. If you can follow every step in the proof, and even write it out by yourself, then you have one degree of understanding. A complementary aspect of really understanding the proof is to be able to show exactly what it means for some simple examples that you can easily grasp. Sometimes it is helpful to take an example you understand well and follow through each step of the proof, applying it to the example you have in mind. Trying to use “lateral thinking” is often important in solving a problem. It is easy to get stuck in one approach to a problem. You need to keep asking yourself if there are other ways to view the problem. Time to reflect is important. You need to do the groundwork in trying to understand the question and in reviewing relevant definitions and theorems from the text. Then you may benefit from simply taking a break and allowing your subconscious mind to sort some things out and make some connections. If you do the preparation well, you will find that a solution or method of attack may occur to you at quite unlikely times, when you are completely relaxed or even absorbed in something unrelated. After emphasizing the use of examples, we need to discuss the next complaint, which is a standard one. “I need more examples.” This is probably true, since even though we have tried to supply a good variety of examples, we may not have included the ones that best tie into your previous TO THE STUDENT xv experience. We can’t overemphasize the importance of examples in providing motivation, as well as in understanding definitions and theorems. Keep in mind that the exercises at the end of each section provide a source for more examples. In fact, each time you learn a new definition you should choose several examples to help you remember the definition. We have tried to present the examples that we feel would be the most helpful in understanding definitions and theorems. This approach is rather different from that in a calculus text, where many examples are simply intended to be “model exercises.” That approach doesn’t work, anyway, in an abstract algebra text, since many exercises by their very nature involve “one of a kind” proofs. For real understanding you must learn to construct your own examples. A good example should be simple enough for you to grasp, but not so simple that it doesn’t illuminate the relevant points. We hope that you will learn to construct good examples for yourself while reading our book. We have drawn our examples from areas that we hope are familiar. We use ordinary addition and multiplication of various sets of numbers, composition of functions, and multiplication of matrices to illustrate the basic algebraic concepts that we want to study. “When I try to find a proof, I don’t know where to start.” Partly, this is just a matter of experience. Just as in any area, it takes some practice before you will feel able to use the various ideas with some ease. It is also probably a matter of some “math anxiety,” because actually doing a proof can seem a little mysterious. How is it possible to come up with all the right ideas, in just the right order? It is true that there are certain approaches that an experienced mathematician would know to try first while attempting to solve a problem. In the text we will try to alert you to these. In fact, sometimes we have suggested a few techniques to keep in mind while attacking the assigned problems. If you get stuck, see what happens in some simple examples. If all else fails, make a list of all of the results in the text that have the hypothesis of your proof as their hypothesis. Also make a list of all those results which have the conclusion of your proof as their conclusion. Then you can use these results to help you narrow the gap between the hypothesis and conclusion of the proof you are working on. “I’m no good at writing proofs.” There are really several parts to proving something: understanding the problem, finding a solution, and writing it down in a logical fashion. What is involved in writing a proof? Isn’t it just an explanation? Of course, it has to include enough detail to be convincing, but it shouldn’t include unnecessary details which might only obscure the real reasons why things work as they do. One way to test this is to see if your proof will convince another student in the class. xvi TO THE STUDENT You should even ask yourself whether or not it will convince you when you read it while studying for the final exam. Constructing a proof is like building a bridge. Construction begins at both ends and continues until it is possible to put in the final span that links both sides. In the same way, in actually constructing a proof, it is often necessary to simplify or rewrite or expand both the hypothesis and the conclusion. You need to try to make the gap between the two as small as possible, so that you can finally see the steps that link them. The bridge is designed to be used by people who simply start at one side and move across to the other. In writing down a proof you should have the same goal, so that a reader can start at the hypothesis and move straight ahead to the conclusion. Writing a clear proof is like any writing—it will probably take several revisions, even after all of the key ideas are in place. (We want to make sure that you don’t suffer from writer’s block because you believe that a proof should appear on your paper, line after line, in perfect order.) Of course, we can’t avoid the real problem. Sometimes the proofs are quite difficult and require a genuine idea. In doing your calculus homework, you may have followed the time-honored technique used by most students. If you couldn’t do a problem, you would look for an example of exactly the same type, reading the text only until you found one. That technique often is good enough to solve routine computational problems, but in a course such as this you should not expect to find models for all of the problems that you are asked to solve as exercises. These problems may very well be unique. The only way to prepare to do them is to read the text in detail. “I keep trying, but I don’t seem to be making any progress.” We can only encourage you to keep trying. Sometimes it seems a bit like learning to ride a bicycle. There is a lot of struggling and effort, trial and error, and it can be really discouraging to see your friends all of a sudden riding pretty well, while you keep falling over. Then one day it just seems to happen—you can do it, and you never really forget how. WRITING PROOFS Logic is the glue that holds together the proofs that you will be writing. Logical connectives such as “and,” “or,” “if : : : then : : :,” and “not” are used to build compound statements out of simpler ones. We assume that you are more or less familiar with these terms, but we need to make a few comments because they are used in mathematics in a precise fashion. Let P and Q be statements, that is, declarative sentences which are either true or false. The word “or” can be ambiguous in ordinary English usage. It may mean TO THE STUDENT xvii “P or Q, but not both,” which we call the exclusive “or,” or it may mean “P or Q, or possibly both,” which we call the inclusive “or.” In mathematics, it is generally agreed to use “or” only in the inclusive sense. That is, the compound statement “P or Q” is true precisely when one of the following occurs: (i) P is true and Q is false; (ii) Q is true and P is false; (iii) P is true and Q is true. The expression “if P then Q” is called a conditional expression, and is the single most important form that we will use. Here P is the hypothesis and Q is the conclusion. By definition, this expression is true in all cases except when P is true and Q is false. In fact, “if P then Q” has the same meaning as “Q or not P.” There are several equivalent ways to say “if P then Q.” We can say “P implies Q,” or “P is sufficient for Q,” or “Q if P,” or “Q necessarily follows from P.” Two expressions related to “if P then Q” are its contrapositive “if not Q then not P” and its converse “if Q then P.” The expression “P implies Q” is logically equivalent to its contrapositive “not Q implies not P,” but is not logically equivalent to its converse “Q implies P.” For example, the most intuitive way to define a one-to-one function f from a set S into a set T is to require that the following condition holds for all x1 ; x2 2 S: if x1 ¤ x2 in S , then f .x1 / ¤ f .x2 /. In practice, though, it is easier to work with equalities, and so the definition is usually reformulated using the contrapositive of the stated condition: if f .x1 / D f .x2 /, then x1 D x2 . The biconditional is the statement “P if and only if Q.” We can also say “P is equivalent to Q,” or “P is necessary and sufficient for Q.” The precision of our mathematical language is abused at one point. Definitions are usually stated in a form such as “a number is said to be even if it is divisible by 2.” It must be understood that the biconditional is being used, since the statement is clearly labeled as a definition, and so the meaning of the definition is “a number is said to be even if and only if it is divisible by 2.” We are now ready to illustrate some techniques of proof: direct proof, and indirect proof. In a direct proof that a statementP implies a statementQ, the proof should begin with the hypothesis thatP is true and end with the conclusion thatQ is true. In an indirect proof we actually prove the contrapositive of the desired result, so the proof should begin with the hypothesis that “not Q” is true and end with the conclusion that “not P” is true. In a proof by contradiction, the proof should begin with the assumption that the conclusion of the theorem is false, and end with a contradiction, in which some statement is shown to be both true and false. We begin with a direct proof of the well-known fact that the square of an even integer is even. To give a convincing proof, we need something concrete to work with, like an equation. We will use the condition that defines a number to be even if it is a multiple of 2. An equivalent condition is that the number can be factored, with 2 as one of the factors. Proposition. If an integer is even, then its square is also even. xviii TO THE STUDENT Proof. Assume that n is an even integer. Then since n has 2 as a factor, we can write n D 2m ; for some integer m. We can square both sides of this equation, to get n2 D .2m/2 D 2.2m2 / : The new equation shows that the square of n has 2 as a factor, and so n2 is an even integer.  You can see that in the proof we began with the hypothesis that n is an even integer, and we ended with the conclusion that n2 is an even integer. To fill in the necessary steps to get from the hypothesis to the conclusion we needed to work with the definition of the terms involved in the statement. We suggest that as a first step you should try, whenever possible, to use definitions and theorems that return you to the more familiar world of high school algebra, with concrete equations involving numbers. The next step is to become familiar with equations that hold in a more general context, say for matrices. Some of the familiar rules will still hold, but some may fail. As one example, contrast this statement from high school algebra: “If both sides of an equation are multiplied by the same number, then the equation is still valid,” with the corresponding statement from matrix theory: “If both sides of a matrix equation are multiplied on the left by the same matrix, then the equation is still valid.” The second statement is similar to the first, but greater care must be taken with matrices, because matrix multiplication does not in general satisfy the commutative law. We next give an example of an indirect proof, in which we prove the contrapositive of the desired result. We will use the fact that adding one to an integer changes its parity, so that it changes from even to odd, or from odd to even. This means that one way to describe all odd integers is to say that they can be expressed as one plus an even integer, so they have the form 2m C 1, for some integer m. This also shows that every integer is either even or odd, but not both. Proposition. If the square of an integer is even, then the integer must be even. Proof. Suppose that the desired conclusion is false. Then the integer in question, say n, must be odd, so it has the form n D 2m C 1 : But then n2 has the form n2 D .2m C 1/2 D 4m2 C 4m C 1 D 2.2m2 C 2m/ C 1 ; which shows that n2 must be odd. Thus the hypothesis that the square is even must be false. We have proved the contrapositive of the desired statement, and this completes the proof.  TO THE STUDENT xix If you have already studied Chapter 1, then you will surely have realized that it is possible to give a direct proof of the previous proposition, based on Lemma 1.2.5. It is called Euclid’s lemma, and states that if p is a prime number that is a factor of the product ab of two integers a and b, then p must be a factor either of a or of b. If we take the special case p D 2, a D n, and b D n, then the lemma reduces to the statement that if p is a factor of n2 , then p must be a factor of n itself. We next give an example of a proof by contradiction. In this method of proof, we assume that the conclusion of the theorem is false, and attempt to arrive at a contradiction. The form of the contradiction should be that some statement is both p true and false. We will prove that 2 is an irrational number, that is, that it cannot be expressed as a quotient of integers, of the form m=n. Proposition. The square root of 2 is an irrational number. Proof. Suppose that the conclusion of the theorem is false, in other words, that is a rational number. Then we can write p m 2D n p 2 for some integers m and n, where n is nonzero. Furthermore, we can cancel common factors of m and n until there are no such common factors left, so we can assume that the fraction m=n has been reduced to lowest terms. Multiplying both sides of the above equation by n, and then squaring both sides, yields the equation 2n2 D m2 : This shows that m2 is an even integer, so by our previous proposition, the number m itself must be even. This means that we can factor 2 out of m, so we can write m D 2k for some integer k. Making this substitution gives 2n2 D .2k/2 D 4k 2 ; and then we can divide both sides of the equation to obtain n2 D 2k 2 : As before, this shows that n2 is even, and it follows that n is even. We have now p reached a contradiction to the assumption that 2 can be written as a fraction m=n in lowest terms, since the numerator and denominator both have 2 as a factor.  Our final proof illustrates that in some cases a great deal of interesting information can be obtained by looking at something from two different points of view. We recall that if n is a positive integer, then the symbol nŠ (read n factorial) is defined xx TO THE STUDENT by nŠ D n.n defined by n
i 1/


2
1. The binomial coefficient (pronounced n choose i) is ! n nŠ D : i iŠ.n i/Š With this notation, the binomial theorem states that
P .a C b/n D niD0 ni ai b n i : The binomial coefficients can be generated recursively. We show the first few by giving part of Pascal’s triangle. 1 1 1 1 1 1 1 1 1 7 8 4 6 15 1 4 1 10 20 35 56 1 3 10 21 28 2 3 5 6 1 5 15 35 70 Proposition. For any positive integer n, we have 1 6 21 56 1 7 28 Pn n
i D0 i 1 8 1 D 2n : Proof. Let S be a set with n elements. We will count the number of subsets of S in two different ways. First, to construct a subset with choose i of the n elements
i elements, we must
of S , and this can be done in n
i ways. Adding ni from i D 0 through n counts P all subsets of S. Thus niD0 ni is the number of subsets of S. On the other hand, when constructing a subset of S, for each of the n elements of S we must choose whether or not to include that element. This gives us a total of 2n choices, and so we conclude that S has 2n subsets. Hence the desired equality holds.  So far we have discussed the construction of the proof of an individual theorem or proposition. Theorems don’t exist in isolation; they are part of a body of results. While studying such a body of results, it is important to step back from time to time to get a global picture. It is of course necessary to note which definitions, theorems, and propositions are used to obtain each result, but it is also important when reviewing a topic to note which theorems are obtained by applying a given result. In order to understand a result’s place in the full scheme of things you should note not only its ancestors, but also its descendents. As you read through a chapter, think of the collection of results as a tapestry woven from individual strands. The true value of each individual theorem only emerges as you see parts of the whole tapestry. HISTORICAL BACKGROUND xxi HISTORICAL BACKGROUND The word “algebra” entered the mathematical vocabulary from Arabic over one thousand years ago, and for almost all of that time it has meant the study of equations. The “algebra” of equations is at a higher level of abstraction than arithmetic, in that symbols may be used to represent unknown numbers. “Modern algebra” or “abstract algebra” dates from the nineteenth century, when problems from number theory and the theory of equations led to the study of abstract mathematical models. In these models, symbols might represent numbers, polynomials, permutations, or elements of various other sets in which arithmetic operations could be defined. Mathematicians attempted to identify the relevant underlying principles, and to determine their logical consequences in very general settings. One of the problems that has motivated a great deal of work in algebra has been the problem of solving equations by radicals. We begin our discussion with the familiar quadratic formula p b ˙ b 2 4ac : x D 2a This formula gives a solution of the equation ax 2 C bx C c D 0, where a ¤ 0, expressed in terms of its coefficients, and using a square root. More generally, we say that an equation an x n C : : : C a1 x C a0 D 0 is solvable by radicals if the solutions can be given in a form that involves sums, differences, products, or quotients of the coefficients an , : : :, a1 , a0 , together with square roots, cube roots, etc., of such combinations of the coefficients. Quadratic and even cubic equations were studied as early as Babylonian times. In the second half of the eleventh century, Omar Khayyam (1048–1131) wrote a book on algebra, which contained a systematic study of cubic equations. His approach was mainly geometric, and he found the roots of the equations as intersections of conic sections. A general method for solving cubic equations numerically eluded the Greeks and later oriental mathematicians. The solution of the cubic equation represented for the Western world the first advance beyond classical mathematics. General cubic equations were reduced to the form x 3 CpxCq D 0. In the early sixteenth century, a mathematician by the name of Scipione del Ferro (1465–1526) solved one particular case of the cubic. He did not publish his solution, but word of the discovery became known, and several others were also successful in solving the equations. The solutions were published in a textbook by Girolamo Cardano (1501–1576) in 1545. This caused a bitter dispute with another mathematician, who had independently discovered the formulas, and claimed to have given them to Cardano under a pledge of secrecy. (For additional details see the notes at the xxii HISTORICAL BACKGROUND end of Chapter 4.) The solution of the equation x 3 Cpx D q was given by Cardano in the form v v s s u u u u 3 3 q p3 q2 t p3 q2 q t C C C C : xD 2 27 4 2 27 4 A solution to the general quartic equation was also given, in which the solution could be expressed in terms of radicals involving the coefficients. (See Section A.6 of the appendix.) Subsequently, attempts were made to find similar solutions to the general quintic equation, but without success. The development of calculus led to methods for approximating roots, and the theory of equations became analytic. One result of this approach was the discovery by Jean le Rond D’Alembert (1717–1783) in 1746 that every algebraic equation of degree n has n roots in the set of complex numbers. Although it was not until 1801 that a correct proof was published, by Carl F. Gauss (1777-1855), this discovery changed the emphasis of the question from the existence of roots to whether equations of degree 5 or greater could be solved by radicals. In 1798, Paolo Ruffini (1765–1822) published a proof claiming to show that the quintic could not be solved by radicals. The proof was not complete, although the general idea was correct. A full proof was finally given by Niels Abel (1802–1829) in 1826. A complete answer to the question of which equations are solvable by radicals was found by Evariste Galois (1811-1832). Galois was killed in a duel, and did not live to see the remarkable consequences of the papers he submitted to the French Academy. (See the introduction to Chapter 8 for further details.) Galois considered certain permutations of the roots of a polynomial—those that leave the coefficients fixed—and showed that the polynomial is solvable by radicals if and only if the associated group of permutations has certain properties. (See the notes at the end of Chapter 3 and the introduction to Chapter 8). This theory, named after Galois, contains deep and very beautiful results, and is the subject of Chapter 8. Although it is not always possible to cover that material in a beginning course in abstract algebra, it is toward this goal that many of the results in this book were originally directed. The penultimate chapter of the book studies the question of unique factorization, in certain subsets of the set of complex numbers, and for polynomials in several variables. Much of the original investigation was motivated by attempts to prove Fermat’s last theorem. (See the introduction to Chapter 9.) The mathematics necessary to answer the question of solvability by radicals and the question of unique factorization includes the development of a good deal of the theory of groups, rings, and fields, which has subsequently been applied in many other areas, including physics and computer science. In studying these areas we have used a modern, axiomatic approach rather than an historical one. Chapter 1 INTEGERS In this chapter we will develop some of the properties of the set of integers Z D f: : : ; 2; 1; 0; 1; 2; : : :g that are needed in our later work. The use of Z for the integers reflects the strong German influence on the modern development of algebra; Z comes from the German word for numbers, “Zahlen.” Some of the computational techniques we study here will reappear numerous times in later chapters. Furthermore, we will construct some concrete examples that will serve as important building blocks for later work on groups, rings, and fields. To give a simple illustration ofhow we will use elementarynumber theory,   0 1 1 0 consider the matrix A D . The powers of A are A2 D ; 1 0 0 1       0 1 1 0 0 1 3 4 5 A D ; A D ; A D ; etc. Since A4 is the 1 0 0 1 1 0 identity matrix I , the powers begin to repeat at A5 , as we can see by writing A5 D A4 A D IA D A ; A6 D A4 A2 D IA2 D A2 ; A7 D A4 A3 D IA3 D A3 ; etc. How can we find A231 , for example? If we divide 231 by 4, we get 57, with remainder 3, so 231 D 4
57 C 3. This provides our answer, since A231 D A4
57C3 D A4
57 A3 D .A4 /57 A3 D I 57 A3 D IA3 D A3 : We can see that two powers Aj and Ak are equal precisely when j and k differ by a multiple of 4. Altogether there are only the following four powers:         1 0 0 1 1 0 0 1 ; ; ; : 0 1 1 0 0 1 1 0 1 2 CHAPTER 1. INTEGERS A very similar situation occurs when we analyze the positive powers of the complex number i . We have i 1 D i , i 2 D 1, i 3 D i , and i 4 D 1. As before, we see that i j D i k if and only if j and k differ by a multiple of 4. As a slightly different example, consider the positive powers of the complex number p 1 3 C i: !D 2 2 There are only three distinct powers of !, as shown below: p 1 3 C i; ! D 2 2 p p ! p ! p 1 3 1 3 1 2 3 3 2 1 3 2 ! D C i C i D iC i D i; 2 2 2 2 4 4 4 2 2 p ! p ! 1 3 1 3 1 3 2 3 2 ! D ! ! D i C i D i D 1: 2 2 2 2 4 4 From this point on, the positive powers begin to repeat, and ! j D ! k if and only if j and k differ by a multiple of 3. To give a unified approach to situations analogous to the ones above, in which we need to consider numbers that exhibit similar behavior when they differ by a multiple of a number n, we will develop the notion of congruence modulo n. The notion of a congruence class will enable us to think of the collection of numbers that behave in the same way as a single entity. The simplest example is congruence modulo 2. When we consider two numbers to be similar if they differ by a multiple of 2, we are just saying that the two numbers are similar if they have the same parity (both are even, or both are odd). Another familiar situation of this type occurs when telling time, since on a clock we do not distinguish between times that differ by a multiple of 12 (or 24 if you are in Europe or the military). In this chapter we will develop only enough number theory to be of use in later chapters, when we study groups, rings, and fields. Historically, almost all civilizations have developed the integers (at least the positive ones) for use in agriculture, commerce, etc. After the elementary operations (addition, subtraction, multiplication, and division) have been understood, human curiosity has taken over and individuals have begun to look for deeper properties that the integers may possess. Nonmathematicians are often surprised that research is currently being done in mathematics. They seem to believe that all possible questions have already been answered. At this point an analogy may be useful. Think of all that is known as being contained in a ball. Adding knowledge enlarges the ball, and this means that the surface of the ball—the interface between known and unknown where research occurs—also becomes larger. In short, the more we know, the more questions there are to ask. In number theory, perhaps more than in any other branch of mathematics, 1.1. DIVISORS 3 there are still many unanswered questions that can easily be posed. In fact, it seems that often the simplest sounding questions require the deepest tools to resolve. One aspect of number theory that has particular applications in algebra is the one that concerns itself with questions of divisibility and primality. Fortunately for our study of algebra, this part of number theory is easily accessible, and it is with these properties of integers that we will deal in this chapter. Number theory got its start with Euclid and much of what we do in the first two sections appears in his book Elements. Our approach to number theory will be to study it as a tool for later use. In the notes at the end of this chapter, we mention several important problems with which number theorists are concerned. You can read the notes at this point, before studying the material in the chapter. In fact, we suggest that you read them now, because we hope to indicate why number theory is so interesting in its own right. 1.1 Divisors Obviously, at the beginning of the book we must decide where to start mathematically. We would like to give a careful mathematical development, including proofs of virtually everything we cover. However, that would take us farther into the foundations of mathematics than we believe is profitable in a beginning course in abstract algebra. As a compromise, we have chosen to assume a knowledge of basic set theory and some familiarity with the set of integers. For the student who is concerned about how the integers can be described formally and how the basic properties of the integers can be deduced, we have provided some very sketchy information in the appendix. Even there we have taken a naive approach, rather than formally treating the basic notions of set theory as undefined terms and giving the axioms that relate them. We have included a list of the Peano postulates, which use concepts and axioms of set theory to characterize the natural numbers. We then give an outline of the logical development of the set of integers, and larger sets of numbers. In the beginning sections of this chapter we will assume some familiarity with the set of integers, and we will simply take for granted some of the basic arithmetic and order properties of the integers. (These properties should be familiar from elementary school arithmetic. They are listed in detail in Section A.3 of the appendix.) The set f0; ˙1; ˙2; : : :g of integers will be denoted by Z throughout the text, while we will use N for the set f0; 1; 2; : : :g of natural numbers. Our first task is to study divisibility. We will then develop a theory of prime numbers based on our work with greatest common divisors. The fact that exact division is not always possible within the set of integers should not be regarded as a deficiency. Rather, it is one source of the richness of the subject of number theory and leads to many interesting and fundamental propositions about the integers. 4 CHAPTER 1. INTEGERS 1.1.1 Definition. An integer a is called a multiple of an integer b if a D bq for some integer q. In this case we also say that b is a divisor of a, and we use the notation b j a. In the above case we can also say that b is a factor of a, or that a is divisible by b. If b is not a divisor of a, meaning that a ¤ bq for any q 2 Z, then we write b6 j a. The set of all multiples of an integer a will be denoted by aZ. Be careful when you use the notation b j a. It describes a relationship between integers a and b and does not represent a fraction. Furthermore, a handwritten vertical line j can easily be confused with the symbol =. The statement 2 j 6 is a true statement; 6 j 2 is a statement that is false. On the other hand, the equation 6=2 D 3 is written correctly, since the fraction 6=2 does represent the number 3. We have at least three different uses for a vertical line: for “such that” in the “setbuilder” notation f j g, when talking about the absolute value of a number, and to indicate that one integer is a divisor of another. We note some elementary facts about divisors. If a ¤ 0 and b j a, then jbj  jaj since jbj  jbjjqj D jaj for some nonzero integer q. It follows from this observation that if b j a and a j b, then jbj D jaj and so b D ˙a. Therefore, if b j 1, then since it is always true that 1 j b, we must have b D ˙1. Note that the only multiple of 0 is 0 itself. On the other hand, for any integer a we have 0 D a
0, and thus 0 is a multiple of any integer. With the notation we have introduced, the set of all multiples of 3 is 3Z = f0; ˙3; ˙6; ˙9; : : :g. To describe aZ precisely, we can write aZ D fm 2 Z j m D aq for some q 2 Zg: Suppose that a is a multiple of b. Then every multiple of a is also a multiple of b, and in fact we can say that a is a multiple of b if and only if every multiple of a is also a multiple of b. In symbols we can write b j a if and only if aZ  bZ. Exercise 18 asks for a more detailed proof of this statement. Before we study divisors and multiples of a fixed integer, we need to state an important property of the set of natural numbers, which we will take as an axiom. 1.1.2 Axiom (Well-Ordering Principle). contains a smallest element. Every nonempty set of natural numbers The well-ordering principle is often used in arguments by contradiction. If we want to show that all natural numbers have some property, we argue that if the set of natural numbers not having the property were nonempty, it would have a least member, and then we deduce a contradiction from this, using the particular facts of the situation. The theory of mathematical induction (see Appendix A.4) formalizes that sort of argument. Let S be a nonempty set of integers that has a lower bound. That is, there is an integer b such that b  n for all n 2 S . If b  0, then S is actually a set of natural 1.1. DIVISORS 5 numbers, so it contains a smallest element by the well-ordering principle. If b < 0, then adding jbj to each integer in S produces a new set T of natural numbers, since n C jbj  0 for all n 2 S . The set T must contain a smallest element, say t, and it is easy to see that t jbj is the smallest element of S . This allows us to use, if necessary, a somewhat stronger version of the well-ordering principle: every set of integers that is bounded below contains a smallest element. The first application of the well-ordering principle will be to prove the division algorithm. In familiar terms, the division algorithm states that dividing an integer a by a positive integer b gives a quotient q and nonnegative remainder r, such that r is less than b. You could write this as a r DqC ; b b but since we are studying properties of the set of integers, we will avoid fractions and write this equation in the form a D bq C r: For example, if a = 29 and b = 8, then 29 D 8
3 C 5; so the quotient q is 3 and the remainder r is 5. You must be careful when a is a negative number, since the remainder must be nonnegative. Simply changing signs in the previous equation, we have 29 D .8/. 3/ C . 5/; which does not give an appropriate remainder. Rewriting this in the form 29 D .8/. 4/ C 3 gives the correct quotient q D 4 and remainder r D 3. Solving for r in the equation a D bq Cr shows that r D a bq, and that r must be the smallest nonnegative integer that can be written in this form, since 0  r < b. This observation clarifies the relationship between the quotient and remainder, and forms the basis of our proof that the division algorithm can be deduced from the well-ordering principle. Another way to see this relationship is to notice that you could find the remainder and quotient by repeatedly subtracting b from a and noting that you have the remainder in the required form when you obtain a nonnegative integer less than b. The next theorem on “long division with remainder” has traditionally been called the “division algorithm”. 6 CHAPTER 1. INTEGERS 1.1.3 Theorem (Division Algorithm). For any integers a and b, with b > 0, there
exist unique integers q (the quotient) and r (the remainder) such that
a D bq C r ; with 0  r < b : Proof. Consider the set R D fa bq W q 2 Zg. The elements of R are the potential remainders, and among these we need to find the smallest nonnegative one. We want to apply the well-ordering principle to the set RC of nonnegative integers in R, so we must first show that RC is nonempty. Since b  1, the number a b. jaj/ D a C b
jaj is nonnegative and belongs to RC , so RC is nonempty. Now by the well-ordering principle, RC has a smallest element, and we will call this element r. We will show that a D bq C r, with 0  r and r < b. By definition, r  0, and since r 2 RC , we must have r D a bq for some integer q. We cannot have r  b, since if we let s D r b we would have s  0 and s D a b.q C 1/ 2 RC . Since s < r, this would contradict the way r was defined, and therefore we must have r < b. We have now proved the existence of r and q satisfying the conditions a D bq C r and 0  r < b. To show that q and r are unique, suppose that we can also write a D bp C s for integers p and s with 0  s < b. We have 0  r < b and 0  s < b, and this implies that js rj < b. But bp C s D bq C r and so s r D b.q p/, which shows that b j .s r/. The only way that b can be a divisor of a number with smaller absolute value is if that number is 0, and so we must have s r D 0, or s D r. Then bp D bq, which implies that p D q since b > 0. Thus the quotient
and remainder are unique, and we have completed the proof of the theorem. 
Given integers a and b, with b > 0, we can use the division algorithm to write
a D bq C r, with 0  r < b. Since b j a if and only if there exists q 2 Z such that a D bq, we see that b j a if and only if r D 0. This simple observation gives us a useful tool in doing number theoretic proofs. To show that b j a we can use the division algorithm to write a D bq C r and then show that r D 0. This technique makes its first appearance in the proof of Theorem 1.1.4. A set of multiples aZ has the property that the sum or difference of two integers in the set is again in the set, since aq1 ˙ aq2 D a.q1 ˙ q2 /. We say that the set aZ is closed under addition and subtraction. This will prove to be a very important property in our later work. The next theorem shows that this property characterizes sets of multiples, since a nonempty set of integers is closed under addition and subtraction if and only if it is a set of the form aZ, for some nonnegative integer a. 1.1.4 Theorem. Let I be a nonempty set of integers that is closed under addition and subtraction. Then I either consists of zero alone or else contains a smallest positive element, in which case I consists of all multiples of its smallest positive element. 1.1. DIVISORS 7 Proof. Since I is nonempty, either it consists of 0 alone, or else it contains a nonzero integer a. In the first case we are done. In the second case, if I contains the nonzero integer a, then it must contain the difference a a D 0, and hence the difference 0 a D a, since I is assumed to be closed under subtraction. Now either a or a is positive, so I contains at least one positive integer. Having shown that the set of positive integers in I is nonempty, we can apply the well-ordering principle to guarantee that it contains a smallest member, say b. Next we want to show that I is equal to the set bZ of all multiples of b. To show that I D bZ, we will first show that bZ  I , and then show that I  bZ. Any nonzero multiple of b is given by just adding b (or b) to itself a finite number of times, so since I is closed under addition, it must contain all multiples of b. Thus bZ  I . On the other hand, to show that I  bZ we must take any element c in I and show that it is a multiple of b, or equivalently, that b j c. (Now comes the one crucial idea in the proof.) Using the division algorithm we can write c D bq C r, for some integers q and r with 0  r < b. Since I contains bq and is closed under subtraction, it must also contain r D c bq. But this is a contradiction unless r D 0, because b was chosen to be the smallest positive integer in I and yet r < b by the division algorithm. We conclude that r D 0, and therefore c D bq, so b j c and we have shown that I  bZ. This completes the proof that I D bZ.  Looking ahead1 . Theorem 1.1.4 will reappear in Chapter 3, when we study cyclic groups, and again in Chapter 5. when we show that Z is a principal ideal domain. One of the main goals of Chapter 1 is to develop some properties of prime numbers, which we will do in Section 1.2. Before discussing prime numbers themselves, we will introduce the notion of relatively prime numbers, and this definition in turn depends on the notion of the greatest common divisor of two numbers. Our definition of the greatest common divisor is given in terms of divisibility, rather than in terms of size, since it is this form that is most useful in writing proofs. Exercise 23 gives an equivalent formulation that focuses on size. 1.1.5 Definition. Let a and b be integers, not both zero. A positive integer d is called the greatest common divisor of a and b if (i) d is a divisor of both a and b, and (ii) any divisor of both a and b is also a divisor of d . The greatest common divisor of a and b will be denoted by gcd.a; b/ or .a; b/. 1 See the related comments in the preface. 8 CHAPTER 1. INTEGERS Our first observation is that gcd.0; 0/ is undefined, but if a is any nonzero integer, then gcd.a; 0/ is defined and equal to jaj. The definition of the greatest common divisor can be shortened by using our notation for divisors. If a and b are integers, not both zero, and d is a positive integer, then d D gcd.a; b/ if (i) d j a and d j b, and (ii) if c j a and c j b, then c j d . The fact that we have written down a definition of the greatest common divisor does not guarantee that there is such a number. Furthermore, the use of the word “the” has to be justified, since it implies that there can be only one greatest common divisor. The next theorem will guarantee the existence of the greatest common divisor, and the question of uniqueness is easily answered: if d1 and d2 are greatest common divisors of a and b, then the definition requires that d1 j d2 and d2 j d1 , so d1 D ˙d2 . Since both d1 and d2 are positive, we have d1 D d2 . If a and b are integers, then we will refer to any integer of the form ma C nb, where m; n 2 Z, as a linear combination of a and b. The next theorem gives a very useful connection between greatest common divisors and linear combinations. 1.1.6 Theorem. Let a and b be integers, not both zero. Then a and b have a greatest common divisor, which can be expressed as the smallest positive linear combination of a and b. Moreover, an integer is a linear combination of a and b if and only if it is a multiple of their greatest common divisor. Proof. Let I be the set of all linear combinations of a and b, that is, I D fx 2 Z j x D ma C nb for some m; n 2 Zg : The set I is nonempty since it contains a D 1
a C 0
b and b D 0
a C 1
b. It is closed under addition and subtraction since if k1 ; k2 2 I , then k1 D m1 a C n1 b and k2 D m2 a C n2 b for some integers m1 ; m2 ; n1 ; n2 . Thus k1 ˙ k2 D .m1 a C n1 b/ ˙ .m2 a C n2 b/ D .m1 ˙ m2 /a C .n1 ˙ n2 /b also belong to I . By Theorem 1.1.4, the set I consists of all multiples of the smallest positive integer it contains, say d . Since d 2 I , we have d D ma C nb for some integers m and n. Since we already know that d is positive, to show that d D .a; b/ we must show that (i) d j a and d j b and (ii) if c j a and c j b, then c j d . First, d is a divisor of every element in I , so d j a and d j b since a; b 2 I . Secondly, if c j a and c j b, say a D cq1 and b D cq2 , then d D ma C nb D m.cq1 / C n.cq2 / D c.mq1 C nq2 / ; which shows that c j d . 1.1. DIVISORS 9 The second assertion follows from the fact that I , the set of all linear combinations of a and b, is equal to d Z, the set of all multiples of d .  You are probably used to finding the greatest common divisor of a and b by first finding their prime factorizations. This is an effective technique for small numbers, but we must postpone a discussion of this method until after we have studied prime factorizations in Section 1.2. In practice, for large numbers it can be very difficult to find prime factors, whereas the greatest common divisor can be found in many fewer steps by using the method we discuss next. The greatest common divisor of two numbers can be computed by using a procedure known as the Euclidean algorithm. (Our proof of the existence of the greatest common divisor did not include an explicit method for finding it.) Before discussing the Euclidean algorithm, we need to note some properties of the greatest common divisor. First, if a and b are not both zero, then it is not difficult to see that gcd.a; b/ D gcd.jaj; jbj/. Furthermore, if b > 0 and b j a, then .a; b/ D b.
The next observation provides the basis for the Euclidean algorithm. If b ¤ 0
and a D bq C r, then .a; b/ D .b; r/. This can be shown by noting first that a is
a multiple of .b; r/ since it is a linear combination of b and r. Then .b; r/ j .a; b/
since b is also a multiple of .b; r/. A similar argument using the equality r D a bq
shows that .a; b/ j .b; r/, and it follows that .a; b/ D .b; r/.
Given integers a > b > 0, the Euclidean algorithm uses the division algorithm repeatedly to obtain
a D bq1 C r1
b D r1 q2 C r2
r1 D r2 q3 C r3
0  r1 < b 0  r2 < r1 0  r3 < r2 with with with etc. If r1 D 0, then b j a, and so .a; b/ D b. Since r1 > r2 > : : : , the remainders
get smaller and smaller, and after a finite number of steps we obtain a remainder
rnC1 D 0. The algorithm ends with the equation
rn
1
D rn qnC1 C 0:
This gives us the greatest common divisor:
.a; b/ D .b; r1 / D .r1 ; r2 / D : : : D .rn
1 ; rn /
D .rn ; 0/ D rn :
Example 1.1.1.
In showing that .24; 18/ D 6, we have .24; 18/ D .18; 6/ since 24 D 18
1 C
6, and .18; 6/ D 6 since 6 j 18. Thus .24; 18/ D .18; 6/ D 6. 
10
CHAPTER 1. INTEGERS
Example 1.1.2.
To show that .126; 35/ D 7, we first have .126; 35/ D .35; 21/ since 126 D
35
3 C 21. Then .35; 21/ D .21; 14/ since 35 D 21
1 C 14, and .21; 14/ D
.14; 7/ since 21 D 14
1 C 7. Finally, .14; 7/ D 7 since 14 D 7
2. Thus
.126; 35/ D .35; 21/ D .21; 14/ D .14; 7/ D 7. 
Example 1.1.3.
In finding .83; 38/, we can arrange the work in the following manner:
83
38
7
3
D
D
D
D
38
2 C 7
7
5C3
3
2C1
3
1
.83; 38/
.38; 7/
.7; 3/
.3; 1/
D
D
D
D
.38; 7/
.7; 3/
.3; 1/
1:
If you only need to find the greatest common divisor, stop as soon as you
can compute it in your head. In showing that .83; 38/ D 1, note that since 7
has no positive divisors except 1 and 7 and is not a divisor of 38, it is clear
immediately that .38; 7/ D 1. 
Example 1.1.4.
Sometimes it is necessary to find the linear combination of a and b that gives
.a; b/. In finding .126; 35/ in Example 1.1.2 we had the following equations:
a
b
r1
r2
D
D
D
D
bq1 C r1
r1 q2 C r2
r2 q3 C d
dq4 C 0
126
35
21
14
D
D
D
D
35
3 C 21
21
1 C 14
14
1 C 7
7
2C0:
The next step is to solve for the nonzero remainder in each of the equations
(omitting the last equation):
r1
r2
d
D a C . q1 /b
D b C . q2 /r1
D r1 C . q3 /r2
21 D 1
126 C . 3/
35
14 D 1
35 C . 1/
21
7 D 1
21 C . 1/
14 :
We then work with the last equation d D r1 C . q3 /r2 , which contains the
greatest common divisor, as desired, but may not be a linear combination of
the original integers a and b. We can obtain the desired linear combination by
substituting for the intermediate remainders, one at a time. Our first equation
is
7
D 1
21 C . 1/
14 :
1.1. DIVISORS
11
We next substitute for the previous remainder 14, using the equation 14 D
1
35 C . 1/
21. This gives the following equation, involving a linear
combination of 35 and 21:
7
D 1
21 C . 1/
Œ1
35 C . 1/
21
D . 1/
35 C 2
21 :
Finally, we use the first equation 21 D 1
126 C . 3/
35 to substitute for the
remainder 21. This allows us to represent the greatest common divisor 7 as a
linear combination of 126 and 35:
7
D . 1/
35 C 2
Œ1
126 C . 3/
35
D 2
126 C . 7/
35 :

The technique introduced in the previous example can easily be extended to the
general situation in which it is desired to express .a; b/ as a linear combination of a
and b. After solving for the remainder in each of the relevant equations, we obtain
r1
r2
r3
r4
D
D
D
D
::
:
aC.
bC.
r1 C .
r2 C .
q1 /b
q2 /r1
q3 /r2
q4 /r3
At each step, the expression for the remainder depends upon the previous two remainders. By substituting into the successive equations and then rearranging terms,
it is possible to express each remainder (in turn) as a linear combination of a and
b. The final step is to express .a; b/ as a linear combination of a and b.
The Euclidean algorithm can be put into a convenient matrix format that keeps
track of the remainders and linear combinations at the same time. To find .a; b/,
the idea is to start with the following system of equations:
x
D a
y D b
and find, by using elementary row operations, an equivalent system of the following
form:
m1 x C n1 y D .a; b/
m2 x C n2 y D 0 :
Beginning with the matrix

1 0 a
0 1 b

;
12
CHAPTER 1. INTEGERS
we use the division algorithm to write a D bq1 C r1 . We then subtract q1 times the
bottom row from the top row, to get

1
0
q1 r1
1
b

:
We next write b D r1 q2 C r2 , and subtract q2 times the top row from the bottom
row. This gives the matrix

1
q1
r1
q2 1 C q1 q2 r2

and it can be checked that this algorithm produces rows in the matrix that give
each successive remainder, together with the coefficients of the appropriate linear
combination of a and b. The procedure is continued until one of the entries in the
right-hand column is zero. Then the other entry in this column is the greatest common divisor, and its row contains the coefficients of the desired linear combination.
Example 1.1.5.
In using the matrix form of the Euclidean algorithm to compute .126; 35/
we begin with the equations x D 126 and y D 35. We have the following
matrices:

1
0
0
1
126
35



Ý
1
0
2
1
7
7
4 14
3 21
1 35



Ý

Ý
2
5
1
1
7 7
18 0
3 21
4 14

Ý

;
ending with the equations 2x 7y D 7 and 5xC18y D 0. Thus .126; 35/ D
7, and substituting x D 126 and y D 35 in the equation 2x 7y D 7 gives
us a linear combination 7 D 2
126 C . 7/
35.
Substituting into the second equation 5x C 81y D 0 also gives us some
interesting information. Any multiple of 0 D . 5/
126 C 18
35 can be
added to the above representation of the greatest common divisor. Thus, for
example, we also have 7 D . 3/
126C11
35 and 7 D . 8/
126C29
35. 
1.1. DIVISORS
13
Example 1.1.6.
In matrix form, the solution for .83; 38/ is the following:






1 0 83
1
2 7
1
2 7
Ý
Ý
0 1 38
0
1 38
5 11 3

11
5
24 1
11 3


Ý
11
38
24 1
83 0
Ý

:
Thus .83; 38/ D 1 and .11/.83/ C . 24/.38/ D 1. 
The number .a; b/ can be written in many different ways as a linear combination of a and b. The matrix method gives a linear combination with 0 D m1 a C
n1 b, so if .a; b/ D ma C nb, then adding the previous equation yields .a; b/ D
.m C m1 /a C .n C n1 /b. In fact, any multiple of the equation 0 D m1 a C n1 b
could have been added, so there are infinitely many linear combinations of a and b
that give .a; b/.
Example 1.1.7 (Difference of squares).
We will prove that if m and n are odd integers, then 4 j .m2
n2 /.
Proof : Since m and n are odd, we can write them in the form m D 2r C 1
and n D 2s C 1, for some integers r and s. Then we can factor m2 n2 to
get .m C n/.m n/, so substituting for m and n gives us
m2
n2 D .2r C 1 C 2s C 1/.2r C 1
1/ D .2/.r C s C 1/.2/.r
s/:
Thus m2 n2 D 4.r C s C 1/.r s/, so we have an expression for m2
that has 4 as a factor, showing that 4 j .m2 n2 /.
n2
2s
Comments: To use the fact that m and n are odd, we needed to find a way to
represent odd integers. Then since we may have m ¤ n, we had to be careful
to use two different variables (r and s) in describing them. Note that there is
a sharper result in Exercise 17. 
Example 1.1.8 (Cube roots of unity).
For the complex number ! D
only if 3 j n, for any integer n.
1
2
C
p
3
i,
2
we will prove that ! n D 1 if and
Proof : Since .a Cbi /.c Cd
i / D .ac bd /C.ad Cbd /i, a short calculation
p
3
1
2
shows that ! D 2
i , and ! 3 D 1. If n 2 Z, and 3 j n, then n D 3q
2
n
for some q 2 Z. Then ! D ! 3q D .! 3 /q D 1q D 1.
14
CHAPTER 1. INTEGERS
Conversely, if n 2 Z and ! n D 1, we can use the division algorithm to
write n D q
3 C r, where the remainder r satisfies 0  r < 3. Then 1 D ! n D ! 3qCr D .! 3 /q ! r D ! r . Since r D 0; 1; 2 and we have shown that ! ¤ 1 and ! 2 ¤ 1, the only possibility is r D 0, and therefore 3 j n.  EXERCISES: SECTION 1.1 Before working on the exercises, you must make sure that you are familiar with all of the definitions and theorems of this section. You also need to be familiar with the techniques of proof that have been used in the theorems and examples in the text. As a reminder, we take this opportunity to list several useful approaches. —When working questions involving divisibility you may find it useful to go back to the definition. If you rewrite b j a as a D bq for some q 2 Z, then you have an equation involving integers, something concrete and familiar to work with. —To show that b j a, try to write down an expression for a that has b as a factor. —Another approach to proving that b j a is to use the division algorithm to write a D bq C r, where 0  r < b, and show that r D 0. —Theorem 1.1.6 is extremely useful in questions involving greatest common divisors. Remember that finding some linear combination of a and b is not necessarily good enough to determine gcd.a; b/. You must show that the linear combination you believe is equal to gcd.a; b/ is actually the smallest positive linear combination of a and b. Exercises with an answer in the text (see “Selected Answers”) are marked by the symbol Ž, while marks those that appear in the supplement “Selected Solutions for Students”. 1. Let m; n; r; s 2 Z. If m2 C n2 D r 2 C s 2 D mr C ns, prove that m D r and n D s. 2. A number n is called perfect if it is equal to the sum of its proper positive divisors (those divisors different from n). The first perfect number is 6 since 1 C 2 C 3 D 6. For each number between 6 and the next perfect number, make a list containing the number, its proper divisors, and their sum. Note: If you reach 40, you have missed the next perfect number. 3. Find the quotient and remainder when a is divided by b. (a) a D 99 ; b D 17 (b) a D 99 ; b D 17 (c) a D 17 ; b D 99 (d) a D 1017 ; b D 99 4. Use the Euclidean algorithm to find the following greatest common divisors. Ž(a) .35; 14/ (b) .15; 11/ Ž(c) .252; 180/ (d) .513; 187/ Ž(e) .7655; 1001/ 1.1. DIVISORS 15 5. Use the Euclidean algorithm to find the following greatest common divisors. (a) .6643; 2873/ (b) .7684; 4148/ (c) .26460; 12600/ (d) .6540; 1206/ (e) .12091; 8439/ 6.ŽFor each part of Exercise 4, find integers m and n such that .a; b/ is expressed in the form ma C nb. 7. For each part of Exercise 5, find integers m and n such that .a; b/ is expressed in the form ma C nb. 8. Let a; b; c be integers. Give a proof for these facts about divisors: (a) If b j a, then b j ac. (b) If b j a and c j b, then c j a. (c) If c j a and c j b, then c j .ma C nb/ for any integers m; n. 9. Let a; b; c be integers such that a C b C c D 0. Show that if n is an integer which is a divisor of two of the three integers, then it is also a divisor of the third. 10. Let a; b; c be integers. (a) Show that if b j a and b j .a C c/, then b j c. (b) Show that if b j a and b6 j c, then b6 j .a C c/. 11. Let a; b; c be integers, with c ¤ 0. Show that bc j ac if and only if b j a. 12. Show that if a > 0, then .ab; ac/ D a.b; c/.
13. Show that if n is any integer, then .10n C 3; 5n C 2/ D 1.
14. Show that if n is any integer, then .a C nb; b/ D .a; b/.
15. For what positive integers n is it true that .n; n C 2/ D 2? Prove your claim.
16. Show that the positive integer n is the difference of two squares if and only if n is
odd or divisible by 4.
17.Show that the positive integer k is the difference of two odd squares if and only if k
is divisible by 8. (This sharpens the result in Example 1.1.7.)
18.Give a detailed proof of the statement in the text that if a and b are integers, then
b j a if and only if aZ  bZ.
19. Let a; b; c be integers, with b > 0; c > 0, and let q be the quotient and r the
remainder when a is divided by b.
(a) Show that q is the quotient and rc is the remainder when ac is divided by bc.
(b) Show that if q 0 is the quotient when q is divided by c, then q 0 is the quotient
when a is divided by bc. (Do not assume that the remainders are zero.)
16
CHAPTER 1. INTEGERS
20. Let a; b; n be integers with n > 1. Suppose that a D nq1 C r1 with 0  r1 < n and b D nq2 C r2 with 0  r2 < n. Prove that n j .a b/ if and only if r1 D r2 . 21. Show that any nonempty set of integers that is closed under subtraction must also be closed under addition. (Thus part of the hypothesis of Theorem 1.1.4 is redundant.) 22. Let a; b; q; r be integers such that b ¤ 0 and a D bq C r. Prove that .a; b/ D .b; r/ by showing that .b; r/ satisfies the definition of the greatest common divisor of a and b. 23. Perhaps a more natural definition of the greatest common divisor is the following: Let a and b be integers, not both zero. An integer d is called the greatest common divisor of the nonzero integers a and b if (i) d j a and d j b, and (ii) c j a and c j b implies d  c. Show that this definition is equivalent to Definition 1.1.5. 24. Show that 3 divides the sum of the cubes of any three consecutive positive integers. 25.ŽFind all integers x such that 3x C 7 is divisible by 11. 26. Prove the following proposition. Let a; b; n 2 Z with .a; b/ D d , and let x0 ; y0 be a particular solution to the equation axCby D n. Then every solution to axCby D n has the form x D x0 C db t, y D y0 da t , for some t 2 Z. Furthermore, for every t 2 Z the integers x D x0 C db t , y D y0 da t , yield a solution to ax C by D n. 27. Prove the following proposition. Let a; b 2 ZC with .a; b/ D 1. Then the equation ax Cby D n has solutions x; y 2 Z with x  0, y  0 if n > ab a b. Moreover,
if n D ab a b, then there are no such solutions.
28. Formulate a definition of the greatest common divisor of three integers a; b; c (not
all zero). With the appropriate definition you should be able to prove that the greatest
common divisor is a linear combination of a, b and c.
1.2
Primes
The main focus of this section is on prime numbers. Our method will be to investigate the notion of two integers which are relatively prime, that is, those which have
no common divisors except ˙1. Using some facts which we will prove about them,
we will be able to prove the prime factorization theorem, which states that every
nonzero integer can be expressed as a product of primes. Finally, we will be able
to use prime factorizations to learn more about greatest common divisors and least
common multiples.
1.2.1 Definition. The nonzero integers a and b are said to be relatively prime if
.a; b/ D 1.
1.2. PRIMES
17
1.2.2 Proposition. Let a; b be nonzero integers. Then .a; b/ D 1 if and only if
there exist integers m; n such that ma C nb D 1.
Proof. If a and b are relatively prime, then by Theorem 1.1.6 integers m and n
can be found for which ma C nb D 1. To prove the converse, we only need to
note that if there exist integers m and n with ma C nb D 1, then 1 must be the
smallest positive linear combination of a and b, and thus .a; b/ D 1, again by
Theorem 1.1.6. 
Proposition 1.2.2 will be used repeatedly in the proof of the next result. A
word of caution—it is tempting to jump from the equation d D ma C nb to the
conclusion that d D .a; b/. For example, 16 D 2
5 C 3
2, but obviously .5; 2/ ¤
16. The most that it is possible to say (using Theorem 1.1.6) is that d is a multiple
of .a; b/. Of course, if maCnb D 1, then Proposition 1.2.2 implies that .a; b/ D 1.
1.2.3 Proposition. Let a; b; c be integers, where a ¤ 0 or b ¤ 0.
(a) If b j ac, then b j .a; b/
c.
(b) If b j ac and .a; b/ D 1, then b j c.
(c) If b j a, c j a and .b; c/ D 1, then bc j a.
(d) .a; bc/ D 1 if and only if .a; b/ D 1 and .a; c/ D 1.
Proof. (a) Assume that b j ac. To show that b j .a; b/
c, we will try to find an
expression for .a; b/
c that has b as an obvious factor. We can write .a; b/ D
ma C nb for some m; n 2 Z, and then multiplying by c gives
.a; b/
c D mac C nbc :
Now b is certainly a factor of nbc, and by assumption it is also a factor of ac, so it
is a factor of mac and therefore of the sum mac C nbc. Thus b j .a; b/
c.
(b) Simply letting .a; b/ D 1 in part (a) gives the result immediately.
(c) If b j a, then a D bq for some integer q. If c j a, then c j bq, so if .b; c/ D 1,
it follows from part (b) that c j q, say with q D cq1 . Substituting for q in the
equation a D bq gives a D bcq1 , and thus bc j a.
(d) Suppose that .a; bc/ D 1. Then ma C n.bc/ D 1 for some integers m and
n, and by viewing this equation as ma C .nc/b D 1 and ma C .nb/c D 1 we can
see that .a; b/ D 1 and .a; c/ D 1.
Conversely, suppose that .a; b/ D 1 and .a; c/ D 1. Then m1 a C n1 b D 1
for some integers m1 and n1 , and m2 a C n2 c D 1 for some integers m2 and n2 .
Multiplying these two equations gives
.m1 m2 a C m1 n2 c C m2 n1 b/a C .n1 n2 /bc D 1;
which shows that .a; bc/ D 1. 
18
CHAPTER 1. INTEGERS
1.2.4 Definition. An integer p > 1 is called a prime number if its only divisors
are ˙1 and ˙p. An integer a > 1 is called composite if it is not prime.
To determine whether or not a given integer n > 1 is prime, we could just
try to divide n by each positive integer less than n. This method of trial division
is very inefficient, and for this reason various sophisticated methods of “primality
testing” have been developed. The need for efficient tests has become particularly
apparent recently, because of applications to computer security that make use of
cryptographic algorithms. To determine the complete list of all primes up to some
bound, there is a useful procedure handed down from antiquity.
Example 1.2.1 (Sieve of Eratosthenes).
The primes less than a fixed positive integer a can be found by the following
procedure. List all positive integers less than a (except 1), and cross off every
even number except 2. Then go to the first number that has not been crossed
off, which will be 3, and cross off all higher multiples of 3. Continue this
process to find all primes less than a. You can stoppafter you have crossed
off all proper multiples of primes p for which p < a, since you will have crossed off every number less than a that p has a proper p factor. (If b is composite, say b D b1 b2 , then either b1  b or b2  b.) For example, we can find allpprimes less than 20 by just crossing off all multiples of 2 and 3, since 5 > 20:
11
2
12
6
3
13
64
14
6
5
15
6
66
16
6
7
17
68
18
6
69
19
10
6
:
This method is attributed to the Greek mathematician Eratosthenes, and is
called the sieve of Eratosthenes.
Similarly, the integers less than a and relatively prime to a can be found by
crossing off the prime factors of a and all of their multiples. For example, the
prime divisors of 36 are 2 and 3, and so the positive integers less than 36 and
relatively prime to it can be found as follows:
1 6 2 6 3 6 4 5 6 6 7 6 8 6 9 10
6
11 12
6
13 14
6
15
6
16
6
17 18
6
19 20
6
21
6
22
6
23 24
6
25 26
6
27
6
28
6
29 30
6
31 32
6
33
6
34
6
35 :

Euclid’s lemma, the next step in our development of the fundamental theorem
of arithmetic, is the one that requires our work on relatively prime numbers. We
will use Proposition 1.2.3 (b) in a crucial way.
1.2.5 Lemma (Euclid). An integer p > 1 is prime if and only if it satisfies the
following property: for all integers a and b, if p j ab, then either p j a or p j b.
1.2. PRIMES
19
Proof. Suppose that p is prime and p j ab. We know that either .p; a/ D p
or .p; a/ D 1, since .p; a/ is always a divisor of p and p is prime. In the first
case p j a and we are done. In the second case, since .p; a/ D 1, we can apply
Proposition 1.2.3 (b) to show that p j ab implies p j b. Thus we have shown that if
p j ab, then either p j a or p j b.
Conversely, suppose that p satisfies the given condition. If p were composite,
then we could writep D ab for some positive integers smaller thanp. The condition
would imply that eitherp j a orp j b, which would be an obvious contradiction. 
The following corollary extends Euclid’s lemma to the product of more than
two integers. In the proof we will use mathematical induction, which we hope is
familiar to you. If you do not remember how to use induction, you should read the
discussion in Appendix A.4.
1.2.6 Corollary. If p is a prime number, and p j a1 a2


an for integers a1 , a2 , : : :,
an , then p j ai for some i with 1  i  n.
Proof. In order to use the principle of mathematical induction, let Pn be the following statement: if p j a1 a2


an , then p j ai for some 1  i  n. The statement P1
is clearly true. Next, assume that the statement Pk is true, that is, if p j a1 a2


ak ,
then p j ai for some 1  i  k. If p j a1 a2


ak akC1 , for integers a1 , a2 , : : :,
ak , akC1 , then applying Euclid’s lemma to a D a1 a2


ak and b D akC1 yields
that p j a1 a2


ak or p j akC1 . In case p j a1 a2


ak , the truth of the statement
Pk implies that p j ai for some 1  i  k. Thus, in either case, p j ai for some
1  i  k C 1, and hence the statement PkC1 is true. By the principle of mathematical induction (as stated in Theorem A.4.2 of Appendix A.4), the statement Pn
holds for all positive integers n. 
The next theorem, on prime factorization, is sometimes called the fundamental
theorem of arithmetic. The naive way to prove that an integer a can be written
as a product of primes is to note that either a is prime and we are done, or else
a is composite, say a D bc. Then the same argument can be applied to b and c,
and continued until a has been broken up into a product of primes. (This process
must stop after a finite number of steps because of the well-ordering principle.)
We also need to prove that any two factorizations of a number are in reality the
same. The idea of the proof is to use Euclid’s lemma to pair the primes in one
factorization with those in the other. In fact, the proof of the uniqueness of the
factorization requires a more delicate argument than the proof of the existence of
the factorization.
20
CHAPTER 1. INTEGERS
1.2.7 Theorem (Fundamental Theorem of Arithmetic). Any integer a > 1 can
be factored uniquely as a product of prime numbers, in the form
a D p1˛1 p2˛2


pn˛n ;
where p1 < p2 < : : : < pn and the exponents ˛1 ; ˛2 ; : : : ; ˛n are all positive. Proof. Suppose that there is some integer greater than 1 that cannot be written as a product of primes. Then the set of all integers a > 1 that have no prime
factorization must be nonempty, so as a consequence of the well-ordering principle
it must have a smallest member, say b. Now b cannot itself be a prime number since
then it would have a prime factorization. Thus b is composite, and we can write
b D cd for positive integers c; d that are smaller than b. Since b was assumed
to be the smallest positive integer not having a factorization into primes, and c
and d are smaller, then both c and d must have factorizations into products of
primes. This shows that b also has such a factorization, which is a contradiction.
Since multiplication is commutative, the prime factors can be ordered in the desired
manner.
If there exists an integer > 1 for which the factorization is not unique, then
by the well-ordering principle there exists a smallest such integer, say a. Assume
ˇ ˇ
ˇ
that a has two factorizations a D p1˛1 p2˛2


pn˛n and a D q1 1 q2 2


qmm , where
p1 < p2 < : : : < pn , and q1 < q2 < : : : < qm , with ˛i > 0 for i D 1; : : : ; n, and
ˇi > 0 for i D 1; : : : ; m. By Corollary 1.2.6 of Euclid’s lemma, q1 j pk for some k
with 1  k  n and p1 j qj for some j with 1  j  m. Since all of the numbers
pi and qi are prime, we must have q1 D pk and p1 D qj . Then p1 D q1 since
q1  qj D p1  pk D q1 . Hence we can let
sD
a
a
D
D p1˛1
p1
q1
1 ˛2
p2
ˇ



pn˛n D q1 1
1 ˇ2
q2
ˇm



qm
:
If s D 1 then a D p1 has a unique factorization, contrary to the choice of a. If
s > 1, then since s < a and s has two factorizations, we again have a contradiction to the choice of a.  If the prime factorization of an integer is known, then it is easy to list all of its divisors. If a D p1˛1 p2˛2


pn˛n , then b is a divisor of a if and only if b D ˇ ˇ ˇ p1 1 p2 2


pn n , where ˇi  ˛i for all i . Thus we can list all possible divisors of a by systematically decreasing the exponents of each of its prime divisors. Example 1.2.2 (Divisor diagrams). The positive divisors of 12 are 1; 2; 3; 4; 6; 12; the positive divisors of 8 are 1; 2; 4; 8; and the positive divisors of 36 are 1; 2; 3; 4; 6; 9; 12; 18; 36. In Figure 1.2.1, we have arranged the divisors so as to show the divisibility relations 1.2. PRIMES 21 among them. There is a path (moving upward only) from a to b if and only if a j b. In constructing the first diagram in Figure 1.2.1, it is easiest to use the prime factorization of 12. Since 12 D 22 3, we first divide 12 by 2 to get 6 and then divide again by 2 to get 3. This gives the first side of the diagram, and to construct the opposite side of the diagram we divide each number by 3. If the number has three different prime factors, then we would need a threedimensional diagram. (Visualize the factors as if on the edges of a box.) With more than three distinct prime factors, the diagrams lose their clarity.  Figure 1.2.1: 12 6 3 @ @ 36 8 @ 4 2 18 4 9 2 1 1 @ 3 @ @ 6 @ @ 12 @ 4 2 1 The following proof, although easy to follow, is an excellent example of the austere beauty of mathematics. 1.2.8 Theorem (Euclid). There exist infinitely many prime numbers. Proof. Suppose that there were only finitely many prime numbers, say p1 , p2 , : : : , pn . Then consider the number a D p1 p2


pn C 1. By Theorem 1.2.7, the number a has a prime divisor, say p. Now p must be one of the primes we listed, so p j .p1 p2


pn /, and since p j a, it follows that p j .a p1 p2


pn /. This is a contradiction since p cannot be a divisor of 1.  Example 1.2.3 (Mersenne numbers). An integer of the form 2n 1, for n 2 ZC , is called a Mersenne number. It has been conjectured that infinitely many Mersenne numbers are prime. Consider the numbers 22 1 D 3, 23 1 D 7, 24 1 D 15, 25 1 D 31, and 26 1 D 63. The prime exponents each give rise to a prime, while the composite exponents each give a composite number. Is this true in general? Continuing to investigate prime exponents gives 27 1 D 127, which is 22 CHAPTER 1. INTEGERS prime, but 211 1 D 2047 D 23
89. Thus a prime exponent may or may not yield a prime number. On the other hand, it is always true that a composite exponent yields a composite number. To prove this, let n be composite, say n D q m (where q and m are integers greater than 1), and consider 2n 1 D 2q m 1. We need to find a nontrivial factorization of 2q m 1 D .2q /m 1. We can look at this as x m 1, and then we have the familiar factorization xm 1 D .x 1/.x m 1 C xm 2 C : : : C x 2 C x C 1/ : Substituting x D 2q shows that 2q 1 is a factor of 2n 1. Now 1 < 2q 1 < 2n 1 since both q and m are greater than 1, and so we have found a nontrivial factorization of 2n 1.  Example 1.2.4 (.2m 1; 2n 1/ D 1 if and only if .m; n/ D 1). Let m and n be positive integers. We will prove that .2m 1; 2n and only if .m; n/ D 1, for any positive integers m and n. 1/ D 1 if Comment: Since this statement is “if and only if”, the proof will have two parts. We first show the “only if” part, since it is shorter. Proof : Suppose that .m; n/ ¤ 1, say .m; n/ D d . Then there exist p; q 2 Z with m D dq and n D dp. The factorization given in Example 1.2.3 shows that 2d 1 is a proper nontrivial divisor of both 2dq 1 and 2dp 1, and therefore .2m 1; 2n 1/ ¤ 1. To prove that .2m 1; 2n 1/ D 1 if .m; n/ D 1, we start by assuming that .m; n/ D 1. Then we can write am C bn D 1 for integers a; b, where we can assume without loss of generality that a < 0 and b > 0. Then, as in
Example 1.2.3, 2m 1 is a factor of 2 am 1, say 2 am 1 D .2m 1/s,
and 2n 1 is a factor of 2bn 1, say 2bn 1 D .2n 1/t , for positive integers
s; t. Then bn D 1 C . a/m, so
.2n
1/t
D 2bn
D 2.2
D 2.2
1 D 21…