7.17 punchline algebra book a

“book2” — 2013/5/24 — 8:18 — page i — #1 i

i

i

i

i

i

Learning Modern Algebra

From Early Attempts to Prove

Fermat’s Last Theorem

i

i

“book2” — 2013/5/24 — 8:18 — page ii — #2 i

i

i

i

i

i

c 2013 by The Mathematical Association of America (Incorporated)

Library of Congress Control Number: 2013940990

Print ISBN: 978-1-93951-201-7

Electronic ISBN: 978-1-61444-612-5

Printed in the United States of America

Current Printing (last digit):

10 9 8 7 6 5 4 3 2 1

i

i

“book2” — 2013/5/24 — 8:18 — page iii — #3 i

i

i

i

i

i

Learning Modern Algebra

From Early Attempts to Prove

Fermat’s Last Theorem

Al Cuoco

EDC, Waltham MA

and

Joseph J. Rotman

University of Illinois at Urbana–Champaign

Published and distributed by

The Mathematical Association of America

i

i

“book2” — 2013/5/24 — 8:18 — page iv — #4 i

i

i

i

i

i

Committee on Books

Frank Farris, Chair

MAA Textbooks Editorial Board

Zaven A. Karian, Editor

Matthias Beck Richard E. Bedient

Thomas A. Garrity

Charles R. Hampton

John Lorch

Susan F. Pustejovsky Elsa J. Schaefer

Stanley E. Seltzer

Kay B. Somers

MAA TEXTBOOKS

Bridge to Abstract Mathematics, Ralph W. Oberste-Vorth, Aristides Mouzakitis, and

Bonita A. Lawrence

Calculus Deconstructed: A Second Course in First-Year Calculus, Zbigniew H. Nitecki

Combinatorics: A Guided Tour, David R. Mazur

Combinatorics: A Problem Oriented Approach, Daniel A. Marcus

Complex Numbers and Geometry, Liang-shin Hahn

A Course in Mathematical Modeling, Douglas Mooney and Randall Swift

Cryptological Mathematics, Robert Edward Lewand

Differential Geometry and its Applications, John Oprea

Elementary Cryptanalysis, Abraham Sinkov

Elementary Mathematical Models, Dan Kalman

An Episodic History of Mathematics: Mathematical Culture Through Problem Solving,

Steven G. Krantz

Essentials of Mathematics, Margie Hale

Field Theory and its Classical Problems, Charles Hadlock

Fourier Series, Rajendra Bhatia

Game Theory and Strategy, Philip D. Straffin

Geometry Revisited, H. S. M. Coxeter and S. L. Greitzer

Graph Theory: A Problem Oriented Approach, Daniel Marcus

Knot Theory, Charles Livingston

Learning Modern Algebra: From Early Attempts to Prove Fermat’s Last Theorem, Al

Cuoco and and Joseph J. Rotman

Lie Groups: A Problem-Oriented Introduction via Matrix Groups, Harriet Pollatsek

Mathematical Connections: A Companion for Teachers and Others, Al Cuoco

Mathematical Interest Theory, Second Edition, Leslie Jane Federer Vaaler and James

W. Daniel

i

i

“book2” — 2013/5/24 — 8:18 — page v — #5 i

i

i

i

i

i

Mathematical Modeling in the Environment, Charles Hadlock

Mathematics for Business Decisions Part 1: Probability and Simulation (electronic text-

book), Richard B. Thompson and Christopher G. Lamoureux

Mathematics for Business Decisions Part 2: Calculus and Optimization (electronic text-

book), Richard B. Thompson and Christopher G. Lamoureux

Mathematics for Secondary School Teachers, Elizabeth G. Bremigan, Ralph J. Bremi-

gan, and John D. Lorch

The Mathematics of Choice, Ivan Niven

The Mathematics of Games and Gambling, Edward Packel

Math Through the Ages, William Berlinghoff and Fernando Gouvea

Noncommutative Rings, I. N. Herstein

Non-Euclidean Geometry, H. S. M. Coxeter

Number Theory Through Inquiry, David C. Marshall, Edward Odell, and Michael Star-

bird

A Primer of Real Functions, Ralph P. Boas

A Radical Approach to Lebesgue’s Theory of Integration, David M. Bressoud

A Radical Approach to Real Analysis, 2nd edition, David M. Bressoud

Real Infinite Series, Daniel D. Bonar and Michael Khoury, Jr.

Topology Now!, Robert Messer and Philip Straffin

Understanding our Quantitative World, Janet Andersen and Todd Swanson

MAA Service Center

P.O. Box 91112

Washington, DC 20090-1112

1-800-331-1MAA FAX: 1-301-206-9789

i

i

“book2” — 2013/5/24 — 8:18 — page vi — #6 i

i

i

i

i

i

i

i

“book2” — 2013/5/24 — 8:18 — page vii — #7 i

i

i

i

i

i

vii

Per Micky: Tutto quello che faccio, lo faccio per te.

i

i

“book2” — 2013/5/24 — 8:18 — page viii — #8 i

i

i

i

i

i

i

i

“book2” — 2013/5/24 — 8:18 — page ix — #9 i

i

i

i

i

i

Contents

Preface xiii

Some Features of This Book . . . . . . . . . . . . . . . . . . . . . xiv

A Note to Students . . . . . . . . . . . . . . . . . . . . . . . . . . xv

A Note to Instructors . . . . . . . . . . . . . . . . . . . . . . . . . xv

Notation xvii

1 Early Number Theory 1

1.1 Ancient Mathematics . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Diophantus . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Geometry and Pythagorean Triples . . . . . . . . . . . . . 8

The Method of Diophantus . . . . . . . . . . . . . . . . . 11

Fermat’s Last Theorem . . . . . . . . . . . . . . . . . . . 14

Connections: Congruent Numbers . . . . . . . . . . . . . . 16

1.3 Euclid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Greek Number Theory . . . . . . . . . . . . . . . . . . . . 21

Division and Remainders . . . . . . . . . . . . . . . . . . 22

Linear Combinations and Euclid’s Lemma . . . . . . . . . 24

Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . 30

1.4 Nine Fundamental Properties . . . . . . . . . . . . . . . . . . 36

1.5 Connections . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Trigonometry . . . . . . . . . . . . . . . . . . . . . . . . 41

Integration . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2 Induction 45

2.1 Induction and Applications . . . . . . . . . . . . . . . . . . . 45

Unique Factorization . . . . . . . . . . . . . . . . . . . . . 53

Strong Induction . . . . . . . . . . . . . . . . . . . . . . . 57

Differential Equations . . . . . . . . . . . . . . . . . . . . 60

2.2 Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . 63

Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . 69

2.3 Connections . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

An Approach to Induction . . . . . . . . . . . . . . . . . . 73

Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . 75

3 Renaissance 81

3.1 Classical Formulas . . . . . . . . . . . . . . . . . . . . . . . 82

3.2 Complex Numbers . . . . . . . . . . . . . . . . . . . . . . . 91

ix

i

i

“book2” — 2013/5/29 — 16:18 — page x — #10 i

i

i

i

i

i

x Contents

Algebraic Operations . . . . . . . . . . . . . . . . . . . . 92

Absolute Value and Direction . . . . . . . . . . . . . . . . 99

The Geometry Behind Multiplication . . . . . . . . . . . . 101

3.3 Roots and Powers . . . . . . . . . . . . . . . . . . . . . . . . 106

3.4 Connections: Designing Good Problems . . . . . . . . . . . . 116

Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Pippins and Cheese . . . . . . . . . . . . . . . . . . . . . 118

Gaussian Integers: Pythagorean Triples Revisited . . . . . . 119

Eisenstein Triples and Diophantus . . . . . . . . . . . . . . 122

Nice Boxes . . . . . . . . . . . . . . . . . . . . . . . . . . 123

Nice Functions for Calculus Problems . . . . . . . . . . . 124

Lattice Point Triangles . . . . . . . . . . . . . . . . . . . . 126

4 Modular Arithmetic 131

4.1 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

4.2 Public Key Codes . . . . . . . . . . . . . . . . . . . . . . . . 149

4.3 Commutative Rings . . . . . . . . . . . . . . . . . . . . . . . 154

Units and Fields . . . . . . . . . . . . . . . . . . . . . . . 160

Subrings and Subfields . . . . . . . . . . . . . . . . . . . . 166

4.4 Connections: Julius and Gregory . . . . . . . . . . . . . . . . 169

4.5 Connections: Patterns in Decimal Expansions . . . . . . . . . 177

Real Numbers . . . . . . . . . . . . . . . . . . . . . . . . 177

Decimal Expansions of Rationals . . . . . . . . . . . . . . 179

Periods and Blocks . . . . . . . . . . . . . . . . . . . . . . 182

5 Abstract Algebra 191

5.1 Domains and Fraction Fields . . . . . . . . . . . . . . . . . . 192

5.2 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

Polynomial Functions . . . . . . . . . . . . . . . . . . . . 204

5.3 Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . 206

Extensions of Homomorphisms . . . . . . . . . . . . . . . 213

Kernel, Image, and Ideals . . . . . . . . . . . . . . . . . . 216

5.4 Connections: Boolean Things . . . . . . . . . . . . . . . . . . 221

Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . 227

6 Arithmetic of Polynomials 233

6.1 Parallels to Z . . . . . . . . . . . . . . . . . . . . . . . . . . 233

Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . 233

Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

Greatest Common Divisors . . . . . . . . . . . . . . . . . 243

Unique Factorization . . . . . . . . . . . . . . . . . . . . . 248

Principal Ideal Domains . . . . . . . . . . . . . . . . . . . 255

6.2 Irreducibility . . . . . . . . . . . . . . . . . . . . . . . . . . 259

Roots of Unity . . . . . . . . . . . . . . . . . . . . . . . . 264

6.3 Connections: Lagrange Interpolation . . . . . . . . . . . . . . 270

7 Quotients, Fields, and Classical Problems 277

7.1 Quotient Rings . . . . . . . . . . . . . . . . . . . . . . . . . 277

7.2 Field Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

Characteristics . . . . . . . . . . . . . . . . . . . . . . . . 287

Extension Fields . . . . . . . . . . . . . . . . . . . . . . . 289

i

i

“book2” — 2013/5/24 — 8:18 — page xi — #11 i

i

i

i

i

i

Contents xi

Algebraic Extensions . . . . . . . . . . . . . . . . . . . . 293

Splitting Fields . . . . . . . . . . . . . . . . . . . . . . . . 300

Classification of Finite Fields . . . . . . . . . . . . . . . . 305 7.3 Connections: Ruler–Compass Constructions . . . . . . . . . . 308

Constructing Regular n-gons . . . . . . . . . . . . . . . . 320

Gauss’s construction of the 17-gon . . . . . . . . . . . . . 322

8 Cyclotomic Integers 329

8.1 Arithmetic in Gaussian and Eisenstein Integers . . . . . . . . 330

Euclidean Domains . . . . . . . . . . . . . . . . . . . . . 333

8.2 Primes Upstairs and Primes Downstairs . . . . . . . . . . . . 337

Laws of Decomposition . . . . . . . . . . . . . . . . . . . 339 8.3 Fermat’s Last Theorem for Exponent 3 . . . . . . . . . . . . 349

Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . 350

The First Case . . . . . . . . . . . . . . . . . . . . . . . . 351

Gauss’s Proof of the Second Case . . . . . . . . . . . . . . 354

8.4 Approaches to the General Case . . . . . . . . . . . . . . . . 359 Cyclotomic integers . . . . . . . . . . . . . . . . . . . . . 360

Kummer, Ideal Numbers, and Dedekind . . . . . . . . . . . 365

8.5 Connections: Counting Sums of Squares . . . . . . . . . . . . 371

A Proof of Fermat’s Theorem on Divisors . . . . . . . . . 373

9 Epilog 379

9.1 Abel and Galois . . . . . . . . . . . . . . . . . . . . . . . . . 379

9.2 Solvability by Radicals . . . . . . . . . . . . . . . . . . . . . 381

9.3 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 9.4 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389

9.5 Wiles and Fermat’s Last Theorem . . . . . . . . . . . . . . . 396

Elliptic Integrals and Elliptic Functions . . . . . . . . . . . 397

Congruent Numbers Revisited . . . . . . . . . . . . . . . . 400

Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . 404

A Appendices 409

A.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409

A.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . 420 A.3 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 424

Bases and Dimension . . . . . . . . . . . . . . . . . . . . 427

Linear Transformations . . . . . . . . . . . . . . . . . . . 435

A.4 Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . 441

A.5 Generalized Associativity . . . . . . . . . . . . . . . . . . . . 442

A.6 A Cyclotomic Integer Calculator . . . . . . . . . . . . . . . . 444 Eisenstein Integers . . . . . . . . . . . . . . . . . . . . . . 445

Symmetric Polynomials . . . . . . . . . . . . . . . . . . . 446

Algebra with Periods . . . . . . . . . . . . . . . . . . . . . 446

References 449

Index 451

About the Authors 459

i

i

“book2” — 2013/5/24 — 8:18 — page xii — #12 i

i

i

i

i

i

i

i

“book2” — 2013/5/24 — 8:18 — page xiii — #13 i

i

i

i

i

i

Preface

This book is designed for college students who want to teach mathematics in

high school, but it can serve as a text for standard abstract algebra courses as

well. First courses in abstract algebra usually cover number theory, groups, and commutative rings. We have found that the first encounter with groups is

not only inadequate for future teachers of high school mathematics, it is also

unsatisfying for other mathematics students. Hence, we focus here on number

theory, polynomials, and commutative rings. We introduce groups in our last

chapter, for the earlier discussion of commutative rings allows us to explain how groups are used to prove Abel’s Theorem: there is no generalization of the

quadratic, cubic, and quartic formulas giving the roots of the general quintic

polynomial. A modest proposal: undergraduate abstract algebra should be a

sequence of two courses, with number theory and commutative rings in the

first course, and groups and linear algebra (with scalars in arbitrary fields) in

the second. We invoke an historically accurate organizing principle: Fermat’s Last The-

orem (in Victorian times, the title of this book would have been Learning Mod-

ern Algebra by Studying Early Attempts, Especially Those in the Nineteenth

Century, that Tried to Prove Fermat’s Last Theorem Using Elementary Meth-

ods). To be sure, another important problem at that time that contributed to modern algebra was the search for formulas giving the roots of polynomials.

This search is intertwined with the algebra involved in Fermat’s Last Theo-

rem, and we do treat this part of algebra as well. The difference between our

approach and the standard approach is one of emphasis: the natural direction

for us is towards algebraic number theory, whereas the usual direction is to- wards Galois theory.

Four thousand years ago, the quadratic formula and the Pythagorean The-

orem were seen to be very useful. To teach them to new generations, it was

best to avoid square roots (which, at the time, were complicated to compute),

and so problems were designed to have integer solutions. This led to Pythag-

orean triples: positive integers a; b; c satisfying a2 C b2 D c2. Two thousand years ago, all such triples were found and, when studying them in the seven-

teenth century, Fermat wondered whether there are positive integer solutions

to an C bn D cn for n > 2. He claimed in a famous marginal note that there are no solutions, but only his proof of the case n D 4 is known. This problem, called Fermat’s Last Theorem, intrigued many of the finest mathematicians, but it long resisted all attempts to solve it. Finally, using sophisticated tech-

niques of algebraic geometry developed at the end of the twentieth century,

Andrew Wiles proved Fermat’s Last Theorem in 1995.

xiii

i

i

“book2” — 2013/5/24 — 8:18 — page xiv — #14 i

i

i

i

i

i

xiv Preface

Before its solution, Fermat’s Last Theorem was a challenge to mathemati-

cians (as climbing Mount Everest was a challenge to mountaineers). There are

no dramatic applications of the result, but it is yet another triumph of human in- tellect. What is true is that, over the course of 350 years, much of contemporary

mathematics was invented and developed in trying to deal with it. The num-

ber theory recorded in Euclid was shown to have similarities with the behavior

of polynomials, and generalizations of prime numbers and unique factoriza-

tion owe their initial study to attempts at proving Fermat’s Last Theorem. But these topics are also intimately related to what is actually taught in high school.

Thus, abstract algebra is not merely beautiful and interesting, but it is also a

valuable, perhaps essential, topic for understanding high school mathematics.

Some Features of This Book

We include sections in every chapter, called Connections, in which we explic- itly show how the material up to that point can help the reader understand and

implement the mathematics that high school teachers use in their profession.

This may include the many ways that results in abstract algebra connect with

core high school ideas, such as solving equations or factoring. But it may also

include mathematics for teachers themselves, that may or may not end up “on the blackboard;” things like the use of abstract algebra to make up good prob-

lems, to understand the foundations of topics in the curriculum, and to place

the topics in the larger landscape of mathematics as a scientific discipline.

Many students studying abstract algebra have problems understanding

proofs; even though they can follow each step of a proof, they wonder how

anyone could have discovered its argument in the first place. To address such problems, we have tried to strike a balance between giving a logical develop-

ment of results (so the reader can see how everything fits together in a coherent

package) and discussing the messier kinds of thinking that lead to discovery

and proofs. A nice aspect of this sort of presentation is that readers participate

in doing mathematics as they learn it. One way we implement this balance is our use of several design features,

such as the Connections sections described above. Here are some others.

� Sidenotes provide advice, comments, and pointers to other parts of the text related to the topic at hand. What could be more fitting for a book related to

Fermat’s Last Theorem than to have large margins? � Interspersed in the text are boxed “callouts,” such as How to Think About

It, which suggest how ideas in the text may have been conceived in the first place, how we view the ideas, and what we guess underlies the formal

exposition. Some other callouts are:

Historical Note, which provides some historical background. It often helps

to understand mathematical ideas if they are placed in historical con-

text; besides, it’s interesting. The biographies are based on those in the MacTutor History of Mathematics Archive of the School of Mathemat-

ics and Statistics, University of St. Andrews, Scotland. It can be found

on the internet: its URL is

www-history.mcs.st-andrews.ac.uk

Etymology, which traces out the origin of some mathematical terms. We

believe that knowing the etymology of terms often helps to understand

the ideas they name.

i

i

“book2” — 2013/5/24 — 8:18 — page xv — #15 i

i

i

i

i

i

Preface xv

Etymology. The word mathematics comes from classical Greek; it

means “knowledge,” “something learned.” But in ancient Rome through

the thirteenth century, it meant “astronomy” and “astrology.” From the

Middle Ages, it acquired its present meaning.

The word arithmetic comes from the Greek word meaning “the art of

counting.” The word geometry, in classical Greek, meant “science of measuring;” it arose from an earlier term meaning “land survey.”

It is a pleasure to acknowledge those who have contributed valuable com-

ments, suggestions, ideas, and help. We thank Don Albers, Carol Baxter, Bruce

Berndt, Peter Braunfeld, Keith Conrad, Victoria Corkery, Don DeLand, Ben Conrad’s website www.math.uconn.edu/

˜kconrad/blurbs/

is full of beautiful ideas.

Fischer, Andrew Granville, Heini Halberstam, Zaven Karian, Tsit-Yuen Lam,

Paul Monsky, Beverly Ruedi, Glenn Stevens, and Stephen Ullom.

A Note to Students

The heart of a mathematics course lies in its problems. We have tried to or-

chestrate them to help you build a solid understanding of the mathematics in

the sections. Everything afterward will make much more sense if you work through as many exercises as you can, especially those that appear difficult.

Quite often, you will learn something valuable from an exercise even if you

don’t solve it completely. For example, a problem you can’t solve may show

that you haven’t fully understood an idea you thought you knew; or it may

force you to discover a fact that needs to be established to finish the solution.

There are two special kinds of exercises.

� Those labeled Preview may seem to have little to do with the section at hand; they are designed to foreshadow upcoming topics, often with numerical ex-

periments.

� Those labeled Take it Further develop interesting ideas that are connected to the main themes of the text, but are somewhat off the beaten path. They

are not essential for understanding what comes later in the text.

An exercise marked with an asterisk, such as 1.8*, means that it is either used in some proof or it is referred to elsewhere in the text. For ease of finding

such exercises, all references to them have the form “Exercise 1.8 on page 6”

giving both its number and the number of the page on which it occurs.

A Note to Instructors

We recommend giving reading assignments to preview upcoming material.

This contributes to balancing experience and formality as described above, and it saves time. Many important pages can be read and understood by students,

and they should be discussed in class only if students ask questions about them.

It is possible to use this book as a text for a three hour one-semester course,

but we strongly recommend that it be taught four hours per week.

—Al Cuoco and Joe Rotman

i

i

“book2” — 2013/5/24 — 8:18 — page xvi — #16 i

i

i

i

i

i

i

i

“book2” — 2013/5/24 — 8:18 — page xvii — #17 i

i

i

i

i

i

Notation

.a; b; c/ 4 triangle with sides of lengths a; b; c

ABC 4 triangle with vertices A;B; C

N 21 natural numbers

Z 21 integers

a j b 21 a is a divisor of b gcd.a; b/ 24 greatest common divisor

bxc 29 greatest integer in x Q 36 rational numbers

R 36 real numbers

) 46 implies lcm.a; b/ 55 least common multiple�

n r

� 63 binomial coefficient

<.z/ 92 real part of complex number z =.z/ 92 imaginary part of complex number z C 92 complex numbers

��! PQ 93 arrow from P to Q

z 96 conjugate of z

jzj 99 modulus of z arg.z/ 100 argument of z

ez 108 complex exponential

�.n/ 111 Euler �-function

N.z/ 116 norm of z

ZŒi  119 Gaussian integers

ZŒ!/ 120 Eisenstein integers

a � b mod m 132 a is congruent to b modulom m1 � � �cmi � � �mr 147 expression withmi deleted

Œa 154 congruence class of integer a

Zm 154 integers mod m

ZŒ� 157 cyclotomic integers

RS 157 ring of functionsR ! S C.X/ 157 ring of continuous functionsX ! R

xvii

i

i

“book2” — 2013/5/24 — 8:18 — page xviii — #18 i

i

i

i

i

i

xviii Notation

Fun.R/ 157 ring of functionsR ! R F4 165 field with 4 elements

2X 167 Boolean ring of subsets of set X

j.m/ 172 calendar month function

Frac.D/ 194 fraction field of domain D

a=b 195 element of Frac.D/

deg.f / 198 degree of polynomial f

RŒŒx 198 all power series over R

RŒx 198 all polynomials over R

x 200 indeterminate inRŒx

f 0.x/ 202 derivative of f .x/ 2 RŒx f # 204 associated polynomial function of f

Poly.R/ 204 all polynomials functions over R

k.x/ 205 field of rational functions over k

Fq 205 finite field with exactly q elements

RŒx1; : : : ; xn 205 polynomials in several variables over R

D.x1; : : : ; xn/ 206 rational functions in several variables over

domain D

R Š S 207 ringsR and S are isomorphic ker' 217 kernel of homomorphism '

im' 217 image of homomorphism '

.b1; : : : ; bn/ 218 ideal generated by b1; : : : ; bn

.a/ 218 principal ideal generated by a

.0/ 219 zero ideal D f0g IJ 220 product of ideals I and J

I C J 220 sum of ideals I and J R � S 221 direct product of rings R and S a _ b 223 binary operation in Boolean ring jAj 227 number of elements in finite set A PID 255 principal ideal domain

UFD 258 unique factorization domain

ˆd .x/ 265 cyclotomic polynomial

aC I 278 coset of element a mod ideal I a � b mod I 279 congruent mod ideal I

R=I 280 quotient ringR mod I˝ X ˛

293 subfield generated by subset X

ŒK W k 291 degree of extension field K=k k.z1 ; : : : ; zn/ 294 extension field adjoining z1; : : : ; zn to k

irr.z; k/ 296 minimal polynomial of z over k

PQ 310 line segment with endpoints P;Q

PQ 310 length of segment PQ

i

i

“book2” — 2013/5/24 — 8:18 — page xix — #19 i

i

i

i

i

i

Notation xix

L.P;Q/ 309 line determined by points P;Q

C.P;Q/ 309 circle with center P , radius PQ

@ 333 size function on Euclidean domain

� 348 � D 1 � ! � 350 valuation

r.n/ 371 number of non-associate z 2 ZŒi  of norm n Q1 372 first quadrant

�.s/ 374 Riemann zeta function

�.n/ 375 a multiplicative function on ZŒi 

Gal.f / 386 Galois group of polynomial f

Gal.E=k/ 387 Galois group of field extension E=k

Sn 389 symmetric group on n letters

G=N 392 quotient group

a 2 A 409 a is an element of set A 1X 411 identity function on set X

f W a 7! b 411 f .a/ D b U � V 410 U is a subset of set V U ¨ V 410 U is a proper subset of V

¿ 410 empty set

g ı f 414 composite f followed by g Œa 421 equivalence class of element a

SpanhXi 427 subspace spanned by subset X dim.V / 433 dimension of vector space V

V � 437 dual space of vector space V

A> 438 transpose of matrix A

i

i

“book2” — 2013/5/24 — 8:18 — page xx — #20 i

i

i

i

i

i

i

i

“book2” — 2013/5/24 — 8:18 — page 1 — #21 i

i

i

i

i

i

1 Early Number Theory Algebra, geometry, and number theory have been used for millennia. Of course,

numbers are involved in counting and measuring, enabling commerce and ar-

chitecture. But reckoning was also involved in life and death matters such as astronomy, which was necessary for navigation on the high seas (naval com-

merce flourished four thousand years ago) as well as to predict the seasons,

to apprise farmers when to plant and when to harvest. Ancient texts that have

survived from Babylon, China, Egypt, Greece, and India provide evidence for

this. For example, the Nile River was the source of life in ancient Egypt, for its banks were the only arable land in the midst of desert. Mathematics was

used by the priestly class to predict flooding as well as to calculate area (taxes

were assessed according to the area of land, which changed after flood waters

subsided). And their temples and pyramids are marvels of engineering.

1.1 Ancient Mathematics

The quadratic formula was an important mathematical tool, and so it was

taught to younger generations training to be royal scribes. Here is a problem from an old Babylonian cuneiform text dating from about 1700 BCE. We quote

from van der Waerden [35], p. 61 (but we write numbers in base 10 instead

of in base 60, as did the Babylonians). We also use modern algebraic notation

that dates from the fifteenth and sixteenth centuries (see Cajori [6]).

I have subtracted the side of the square from the area, and it is 870. What

is the side of my square?

The text rewrites the data as the quadratic equation x2 � x D 870; it then gives a series of steps showing how to find the solution, illustrating that the

Babylonians knew the quadratic formula.

Historians say that teaching played an important role in ancient mathe- matics (see van der Waerden [35], pp. 32–33). To illustrate, the coefficients

of the quadratic equation were chosen wisely: the discriminant b2 � 4ac D 1 � 4.�870/ D 3481 D 592 is a perfect square. Were the discriminant not a The number 59 may have

been chosen because

the Babylonians wrote

numbers in base 60, and

59 D 60 � 1.

perfect square, the problem would have been much harder, for finding square

roots was not routine in those days. Thus, the quadratic in the text is well- chosen for teaching the quadratic formula; a good teaching prize would not be

awarded for x2 � 47x D 210. The Babylonians were not afraid of cubics. Another of their problems from

about the same time is

1

i

i

“book2” — 2013/5/24 — 8:18 — page 2 — #22 i

i

i

i

i

i

2 Chapter 1 Early Number Theory

Solve 12x3 D 3630,

and the answer was given. The solution was, most likely, obtained by using tables of approximations of cube …