Punchline algebra book a 2.10

Quotient Rings

i

“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 roots.

A standard proof of the quadratic formula is by “completing the square.”

This phrase can be taken literally. Given a quadratic x2C bx D c with b and c positive, we can view x2 C bx as the shaded area in Figure 1.1. Complete the

x

x

Figure 1.1. Completing the Square.

figure to a square by attaching the corner square having area 1 2 b � 1

2 b D 1

4 b2;

the new square has area

c C 1 4 b2 D x2 C bx C 1

4 b2 D .x C 1

2 b/2:

Thus, x C 1 2 b D

q c C 1

4 b2, which simplifies to the usual formula giving

the roots of x2 C bx � c. The algebraic proof of the validity of the quadratic

In [35], pp. 26–35, van

der Waerden considers

the origin of proofs in

mathematics, suggesting

that they arose in Europe

and Asia in Neolithic

(late Stone Age) times,

4500 BCE–2000 BCE.

formula works without assuming that b and c are positive, but the idea of the

proof is geometric.

a2

b2

a

b

a

b

a b

a

b

c2

Figure 1.2. Pythagorean Theorem.

The Babylonians were aware of the Pythagorean Theorem. Although they

believed it, there is no evidence that the Babylonians had proved the Pythag-

orean Theorem; indeed, no evidence exists that they even saw a need for a

proof. Tradition attributes the first proof of this theorem to Pythagoras, who Exercise 1.4 on page 5

asks you to show that the

rhombus in Figure 1.2

with sides of length c is a

square.

lived around 500 BCE, but no primary documents extant support this. An ele-

gant proof of the Pythagorean Theorem is given on page 354 of Heath’s 1926

translation [16] of Euclid’s The Elements; the theorem follows from equality

of the areas of the two squares in Figure 1.2.

i

i

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

i

i

i

i

i

1.1 Ancient Mathematics 3

Here is an ancient application of the Pythagorean Theorem. Aristarchus

(ca. 310 BCE–250 BCE) saw that the Moon and the Sun appear to be about

the same size, and he wondered how far away they are. His idea was that at the time of the half-moon, the Earth E , Moon M , and Sun S form a right

triangle with right angle †M (that is, looking up at the Moon, the line of sight seems to be perpendicular to the Sun’s rays). The Pythagorean Theorem gives

a

S M

E

Figure 1.3. Earth, Moon, and Sun.

jSEj2 D jSM j2 C jMEj2. Thus, the Earth is farther from the Sun than it is from the Moon. Indeed, at sunset, ˛ D †E seems to be very close to 90ı: if we are looking at the Moon and we wish to watch the Sun dip below the horizon,

we must turn our head all the way to the left. Aristarchus knew trigonometry;

he reckoned that cos˛ was small, and he concluded that the Sun is very much

further from the Earth than is the Moon.

Example 1.1. Next, we present a geometric problem from a Chinese collec-

tion of mathematical problems, Nine Chapters on the Mathematical Art, writ- ten during the Han Dynasty about two thousand years ago. Variations of this

problem still occur in present day calculus books!

There is a door whose height and width are unknown, and a pole whose There are similar problems from the Babylonians and

other ancient cultures. length p is also unknown. Carried horizontally, the pole does not fit by 4

ch’ihI vertically, it does not fit by 2 ch’ihI slantwise, it fits exactly. What are the height, width, and diagonal of the door?

p p – 2

p – 4

Figure 1.4. Door Problem.

The data give a right triangle with sides p � 4, p � 2, and p, and the Py- thagorean Theorem gives the equation .p � 4/2 C .p � 2/2 D p2, which simplifies to p2�12pC20 D 0. The discriminant b2�4ac is 144�80 D 64, a perfect square, so that p D 10 and the door has height 8 and width 6 (the other root of the quadratic is p D 2, which does not fit the physical data). The sides of the right triangle are 6, 8, 10, and it is similar to the triangle with

sides 3; 4; 5. Again, the numbers have been chosen wisely. The idea is to teach

i

i

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

i

i

i

i

i

4 Chapter 1 Early Number Theory

students how to use the Pythagorean Theorem and the quadratic formula. As

we have already remarked, computing square roots was then quite difficult, so

that the same problem for a pole of length p D 12 would not have been very bright because there is no right triangle with sides of integral length that hasThe word hypotenuse

comes from the Greek verb

meaning to stretch. hypotenuse 12. N

Are there right triangles whose three sides have integral length that are not

similar to the 3; 4; 5 triangle? You are probably familiar with the 5; 12; 13 tri-

angle. Let’s use 4.a; b; c/ (lower case letters) to denote the triangle whose sides have length a, b, and c; if 4.a; b; c/ is a right triangle, then c denotes the length of its hypotenuse, while a and b are its legs. Thus, the right trian-

gle with side-lengths 5, 12, 13 is denoted by 4.5; 12; 13/. (We use the usual notation, 4ABC , to denote a triangle whose vertices are A;B; C .)

Definition. A triple .a; b; c/ of positive integers with a2 C b2 D c2 is called a Pythagorean triple.

If .a; b; c/ is a Pythagorean triple, then the triangles 4.a; b; c/ and 4.b; a; c/ are the same. Thus, we declare that the Pythagorean triples .a; b; c/ and .b; a; c/ are the same.

Historical Note. Pythagorean triples are the good choices for problems teach-

ing the Pythagorean Theorem. There are many of them: Figure 1.5 shows a

Babylonian cuneiform tablet dating from the dynasty of Hammurabi, about

1800 BCE, whose museum name is Plimpton 322, which displays fifteen Pythagorean triples (translated into our number system).

b a c

120 119 169

3456 3367 4825

4800 4601 6649

13500 12709 18541

72 65 97

360 319 481

2700 2291 3541

960 799 1249

600 481 769

6480 4961 8161

60 45 75

2400 1679 2929

240 161 289

2700 1771 3229

90 56 106

Figure 1.5. Plimpton 322.

i

i

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

i

i

i

i

i

1.1 Ancient Mathematics 5

It is plain that the Babylonians had a way to generate large Pythagorean

triples. Here is one technique they might have used. Write

a2 D c2 � b2 D .c C b/.c � b/:

If there are integers m and n with

c C b D m2

c � b D n2;

then

a D p .c C b/.c � b/ D mn: (1.1)

We can also solve for b and c:

b D 1 2

� m2 � n2

� (1.2)

c D 1 2

� m2 C n2

� : (1.3)

Summarizing, here is what we call the Babylonian method. Choose odd num-

bers m and n (forcing m2 C n2 and m2 � n2 to be even, so that b and c are integers), and define a, b, and c by Eqs. (1.1), (1.2), and (1.3). For example, if m D 7 and n D 5, we obtain 35, 12, 37. If we choose m D 179 and n D 71, we obtain 13500, 12709, 18541, the largest triple on Plimpton 322.

The Babylonian method does not give all Pythagorean triples. For example,

.6; 8; 10/ is a Pythagorean triple, but there are no odd numbers m > n with

6 D mn or 8 D mn. Of course, .6; 8; 10/ is not signifcantly different from .3; 4; 5/, which arises from 3 > 1. In the next section, we will show, follow-

ing Diophantus, ca. 250 CE, how to find all Pythagorean triples. But now we

should recognize that practical problems involving applications of pure math-

ematics (e.g., surveying) led to efforts to teach this mathematics effectively,

which led to more pure mathematics (Pythagorean triples) that seems at first to After all, what practi-

cal application does

the Pythagorean triple

.13500; 12709; 18541/

have?

have no application outside of teaching. The remarkable, empirical, fact is that pure mathematics yields new and valuable applications. For example, we shall

see in the next section that classifying Pythagorean triples leads to simplifying

the verification of some trigonometric identities as well as the solution of cer-

tain integration problems (for example, we will see a natural way to integrate

sec x).

Exercises

1.1 Prove the quadratic formula for the roots of ax2Cbx Cc D 0 whose coefficients a, b, and c may not be positive.

1.2 Give a geometric proof that .a C b/2 D a2 C 2ab C b2 for a; b positive. 1.3 * Let f .x/ D ax2C bx C c be a quadratic whose coefficients a; b; c are rational.

Prove that if f .x/ has one rational root, then its other root is also rational.

1.4 *

(i) Prove that the rhombus with side lengths c in the left square of Figure 1.2 is The book by Loomis [20] contains 370 different

proofs of the Pythagorean

Theorem, by the author’s

count.

a square.

(ii) Prove the Pythagorean Theorem in a way suggested by Figure 1.2.

(iii) Give a proof of the Pythagorean Theorem different from the one suggested

by Figure 1.2.

HELIANG GAO
高亮
HELIANG GAO
高亮
HELIANG GAO
高亮
HELIANG GAO
高亮
i

i

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

i

i

i

i

i

6 Chapter 1 Early Number Theory

1.5 Here is another problem from Nine Chapters on the Mathematical Art. A pond is

10 ch’ih square. A reed grows at its center and extends 1 ch’ih out of the water.

If the reed is pulled to the side of the pond, it reaches the side precisely. What are

the depth of the water and the length of the reed?

Answer: Depth = 12 ch’ih and length = 13 ch’ih.

1.6 *

(i) Establish the algebraic identity

� a C b

2

�2 � �

a � b 2

�2 D ab:

(ii) Use (i) to establish the Arithmetic–Geometric Mean Inequality: if a and b

are positive reals, then

p ab � 12 .a C b/:

When is there equality?

(iii) Show how to dissect an a � b rectangle so that it fits inside a square with side-length .a C b/=2. How much is “left over?”

Hint: Try it with numbers. Cut an 8 � 14 rectangle to fit inside an 11 � 11 square.

(iv) Show that a rectangle of maximum area with fixed perimeter is a square.

(v) The hyperbolic cosine is defined by

cosh x D 12 .e x C e�x/:

Prove that cosh x � 1 for all real numbers x, while coshx D 1 if and only if x D 0.

(vi) Use Figure 1.6 to give another proof of the Arithmetic-Geometric Mean In-

equality.

a b

Figure 1.6. Arithmetic–Geometric Mean Inequality.

1.7 * Prove that there is no Pythagorean triple .a; b; c/ with c D 12.

1.8 * Let .a; b; c/ be a Pythagorean triple.

(i) Prove that the legs a and b cannot both be odd.

(ii) Show that the area of 4.a; b; c/ is an integer.

HELIANG GAO
高亮
i

i

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

i

i

i

i

i

1.2 Diophantus 7

1.9 * Show that 5 is not the area of a triangle whose side-lengths form a Pythagorean

triple.

1.10 * Let .a; b; c/ be a Pythagorean triple. If m is a positive integer, prove that

.ma; mb; mc/ is also a Pythagorean triple.

1.11 .Converse of Pythagorean Theorem/: * Let 4 D 4.a; b; c/ be a triangle with sides of lengths a; b; c (positive real numbers, not necessarily integers). Prove that

if a2 C b2 D c2, then 4 is a right triangle.

Hint: Construct a right triangle 40 with legs of lengths a; b, and prove that 40 is congruent to 4 by side-side-side.

1.12 * Prove that every Pythagorean triple .a; b; c/ arises from a right triangle 4.a; b; c/ having sides of lengths a; b; c.

1.13 If P D .a; b; c/ is a Pythagorean triple, define r.P / D c=a. If we label the Py- thagorean triples on Plimpton 322 as P1; : : : ; P15 , show that r.Pi / is decreasing:

r.Pi / > r.PiC1/ for all i � 14.

1.14 * If .a; b; c/ is a Pythagorean triple, show that .a=c; b=c/ is a point on the graph

of x2 C y2 D 1. What is the graph of x2 C y2 D 1?

1.15 Preview: Let L be the line through .�1; 0/ with slope t . (i) If t D 12 , find all the points where L intersects the graph of x

2 C y2 D 1.

Answer: .35 ; 4 5 /.

(ii) If t D 32 , find all the points where L intersects the graph of x2 C y2 D 1.

Answer: . �513 ; 12 13

/.

(iii) Pick a rational number t , not 12 or 3 2 , and find all the points where L intersects

the graph of x2 C y2 D 1. (iv) Suppose ` is a line that contains .�1; 0/ with slope r . If r is a rational number,

show that ` intersects the graph of x2 C y2 D 1 in two points, each of which has rational number coordinates.

1.16 Preview: A Gaussian integer is a complex number a C bi where both a and b are integers. Pick six Gaussian integers r C si with r > s > 0 and square them. State something interesting that you see in your results.

1.17 Preview: Consider a complex number z D q C ip, where q > p are positive integers. Prove that

.q2 � p2; 2qp; q2 C p2/

is a Pythagorean triple by showing that jz2j D jzj2.

If z is a complex number,

say z D aC bi , then we define jzj D

p a2 C b2.

1.18 Preview: Show, for all real numbers m and n, that

h 1 2 .m C n/ C

1 2 .m � n/i

i2 D mn C 12 .m

2 � n2/i:

1.2 Diophantus

We are going to classify Pythagorean triples using a geometric method of Dio-

phantus that describes all Pythagorean triples.

Historical Note. We know very little about the life of Diophantus. He was

a mathematician who lived in Alexandria, Egypt, but his precise dates are