Description

two abstract questions, problem 9 and problem 10 attachments is the lemma and definition you may need for the questions

DO NOT count on answers on Chegg or coursehero.., most of them are incorrect.

6 attachmentsSlide 1 of 6attachment_1attachment_1attachment_2attachment_2attachment_3attachment_3attachment_4attachment_4attachment_5attachment_5attachment_6attachment_6

Unformatted Attachment Preview

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:math:niu: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 ni 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 A457C3 D A457 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

75C3

32C1

31

.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

72C0:

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

Ý

2

1

7

4

1

0

3 21

1 35

7

14

Ý

Ý

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/126C1135 and 7 D . 8/126C2935.

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 1 D 21C. a/m 1

D 2.2 am / 1 D 2.2 am 1/ C 2

D 2.2m 1/s C 1

1

and therefore t .2n 1/ 2s.2m 1/ D 1. This shows that .2m 1; 2n 1/ D 1,

and completes the proof.

The final concept we study in this section is the least common multiple of two

integers. Its definition is parallel to that of the greatest common divisor. We can

characterize it in terms of the prime factorizations of the two numbers, or by the

fact that the product of two numbers is equal to the product of their least common

multiple and greatest common divisor.

1.2. PRIMES

23

1.2.9 Definition. A positive integer m is called the least common multiple of the

nonzero integers a and b if

(i) m is a multiple of both a and b, and

(ii) any multiple of both a and b is also a multiple of m.

We will use the notation lcmŒa; b or Œa; b for the least common multiple of a and

b.

When written out in symbols, the definition of the least common multiple looks

like this: m D lcmŒa; b if (i) a j m and b j m, and (ii) if a j c and b j c, then m j c.

There are times, as in next proposition, when it is convenient to allow the prime

factorization of a number to include primes with exponent 0. This leads to a representation that is no longer unique, but it is particularly useful to be able to write the

prime factorizations of two different integers in terms of the same primes.

1.2.10 Proposition. Let a and b be positive integers with prime factorizations a D

ˇ

ˇ

ˇ

p1˛1 p2˛2 pn˛n and b D p1 1 p2 2 pn n , where ˛i 0 and ˇi 0 for all i .

(a) Then a j b if and only if ˛i ˇi for i D 1; 2; : : : ; n.

(b) For each i , let ıi D minf˛i ; ˇi g and i D maxf˛i ; ˇi g. Then

gcd.a; b/ D p1ı1 p2ı2 pnın and lcmŒa; b D p1 1 p2 2 pnn :

Proof. (a) Suppose that ˛i ˇi for i D 1; 2; : : : ; n. Let i D ˇi ˛i , for

i D 1; 2; : : : ; n, and set c D p11 p22 pnn (note that i 0 for i D 1; 2; : : : ; n).

Then

˛ C

ac D p1˛1 p2�…

Purchase answer to see full

attachment

Tags:

polynomials

coefficients

isomorphic extensions

algebraic closure

non empty set of injections

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.

## Reviews, comments, and love from our customers and community:

This page is having a slideshow that uses Javascript. Your browser either doesn't support Javascript or you have it turned off. To see this page as it is meant to appear please use a Javascript enabled browser.