First course in abstract algebra: with applications
Joseph J. RotmanThis text introduces readers to the algebraic concepts of group and rings, providing a comprehensive discussion of theory as well as a significant number of applications for each.
Number Theory: Induction; Binomial Coefficients; Greatest Common Divisors; The Fundamental Theorem of Arithmetic
Congruences; Dates and Days. Groups I: Some Set Theory; Permutations; Groups; Subgroups and Lagrange's Theorem; Homomorphisms; Quotient Groups; Group Actions; Counting with Groups. Commutative Rings I: First Properties; Fields; Polynomials; Homomorphisms; Greatest Common Divisors; Unique Factorization; Irreducibility; Quotient Rings and Finite Fields; Officers, Magic, Fertilizer, and Horizons. Linear Algebra: Vector Spaces; Euclidean Constructions; Linear Transformations; Determinants; Codes; Canonical Forms. Fields: Classical Formulas; Insolvability of the General Quintic; Epilog. Groups II: Finite Abelian Groups; The Sylow Theorems; Ornamental Symmetry. Commutative Rings III: Prime Ideals and Maximal Ideals; Unique Factorization; Noetherian Rings; Varieties; Grobner Bases.
For all readers interested in abstract algebra.
 Open in Browser
 Checking other formats...
 Convert to EPUB
 Convert to FB2
 Convert to MOBI
 Convert to TXT
 Convert to RTF
 Converted file can differ from the original. If possible, download the file in its original format.
 Please login to your account first

Need help? Please read our short guide how to send a book to Kindle.
Please note you need to add our email km@bookmail.org to approved email addresses. Read more.
You may be interested in
Most frequently terms


Special Notation Set Theory and Number Theory n r bxc 8d (x) φ(n) ab (a, b) [a, b] a ≡ b mod m X ⊆Y X Y X ×Y 1X X  im f f : a 7→ b a≡b [a] [a] m natural numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 binomial coefficient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 greatest integer in x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 dth cyclotomic polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Euler φfunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 rational numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 real numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 complex numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 a is a divisor of b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 gcd of a and b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 lcm of a and b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 a congruent to b mod m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 X is subset of Y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 X is proper subset of Y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81 empty set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 cartesian product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 identity function on set X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 number of elements in finite set X . . . . . . . . . . . . . . . . . . . . . . . 84 image of function f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 f (a) = b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 a is equivalent to b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 equivalence class of a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 congruence class of a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 integers modulo m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 i x 1 , .., xbi , .., x n x 1 , . . . , x n with x i deleted . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 δi j Kronecker delta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 Group Theory SX Sn sgn(α) GL(n, k) Isom( 2 ) O2 ( ) D2n 6(2, R) V H≤G H <G An aH [G : H ] SL(n, k) G∼ =H ker f H G Z (G) Q G/H H×K Gx (x) C G (a) GL(V ) H⊕K P n Lni=1 Si i=1 Si NG (H ) UT(n, k) symmetric group on set X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 symmetric group on n letters . . . . . . . . . . . . . . . . . . . . . . . . . . 103 signum of permutation α . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 general linear group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 group of isometries of the plane . . . . . . . . . . . . . . . . . . . . . . . . 136 orthogonal group of the plane . . . . . . . . . . . . . . . . . . . . . . . . . . 136 dihedral group of order 2n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 stochastic group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 fourgroup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 H is subgroup of G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 H is proper subgroup of G . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 alternating group on n letters . . . . . . . . . . . . . . . . . . . . . . . . . . 147 coset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 index of H in G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 special linear group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 isomorphic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 kernel of f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 H is normal subgroup of G . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 center of group G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 quaternion group of order 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 quotient group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 direct product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 stabilizer of x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 orbit of x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 centralizer of a ∈ G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 all automorphisms of vector space V . . . . . . . . . . . . . . . . . . . 381 direct sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473 sum of subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 direct sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 normalizer of H ≤ G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 unitriangular group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493 Commutative Rings and Linear Algebra I or In identity matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 [i ] Gaussian integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 ( ) ring of functions on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 (X ) U (R) (R) p, q Frac(R) R× deg( f ) k[x] k(x) k[[x]] R∼ =S (a1 , . . . , an ) (a) R×S a+I R/I k(z) A◦B A⊗B Matn (k) AT Row( A) Col( A) dim(V ) E/k [E : k] Homk (V , W ) Y [T ] X det( A) tr( A) Supp(w) Gal(E/k) Var(I ) Id(V √) I DEG ( f ) Boolean ring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 group of units in ring R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 ring of functions on ring R . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 finite field having p, or q, elements . . . . . . . . . . . . . . . . . . . . 228 fraction field of domain R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 nonzero elements in ring R . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 degree of polynomial f (x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 polynomial ring over k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 field of rational functions over k . . . . . . . . . . . . . . . . . . . . . . . 238 power series ring over k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 isomorphic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 ideal generated by a1 , . . . , an . . . . . . . . . . . . . . . . . . . . . . . . . . 246 principal ideal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 direct product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 coset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 quotient ring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 adjoining z to field k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 Hadamard product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 Kronecker product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 all n × n matrices over k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 transpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 row space of matrix A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 column space of matrix A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 dimension of vector space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 field extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 degree of field extension E/k . . . . . . . . . . . . . . . . . . . . . . . . . . 341 all linear transformations V → W . . . . . . . . . . . . . . . . . . . . . 367 matrix of transformation T relative to bases X , Y . . . . . . . . 370 determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385 trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392 support of w ∈ k n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 Galois group of E/k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452 algebraic set of ideal I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540 ideal of algebraic set V . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544 radical of ideal I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545 multidegree of polynomial f (x 1 , . . . , x n ) . . . . . . . . . . . . . . . 559 A FIRST COURSE IN ABSTRACT ALGEBRA Third Edition JOSEPH J. ROTMAN University of Illinois at UrbanaChampaign PRENTICE HALL, Upper Saddle River, New Jersey 07458 To my two wonderful kids, Danny and Ella, whom I love very much Contents Special Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v Preface to the Third Edition . . . . . . . . . . . . . . . . . . . . . viii Chapter 1 Section 1.1 Section 1.2 Section 1.3 Section 1.4 Section 1.5 Section 1.6 Chapter 2 Number Theory . . . . . . . . . . . . . . . . . . . . . Induction . . . . . . . . . . . . . . . . . Binomial Coefficients . . . . . . . . . . Greatest Common Divisors . . . . . . . The Fundamental Theorem of Arithmetic Congruences . . . . . . . . . . . . . . . Dates and Days . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Groups I . . . . . . . . . . . . . . . . . . . . . . . . . . Section 2.1 Some Set Theory . . . . . . . . . . . Functions . . . . . . . . . . . . . . . . . . . Equivalence Relations . . . . . . . . . . . . . Section 2.2 Permutations . . . . . . . . . . . . . Section 2.3 Groups . . . . . . . . . . . . . . . . Symmetry . . . . . . . . . . . . . . . . . . . Section 2.4 Subgroups and Lagrange’s Theorem Section 2.5 Homomorphisms . . . . . . . . . . . Section 2.6 Quotient Groups . . . . . . . . . . . Section 2.7 Group Actions . . . . . . . . . . . . Section 2.8 Counting with Groups . . . . . . . . Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 16 34 53 57 72 80 80 83 96 103 121 134 144 155 168 189 205 Commutative Rings I . . . . . . . . . . . . . . . . . 214 v vi C ONTENTS Section 3.1 First Properties . . . . . . . . . . . . . . Section 3.2 Fields . . . . . . . . . . . . . . . . . . . Section 3.3 Polynomials . . . . . . . . . . . . . . . Section 3.4 Homomorphisms . . . . . . . . . . . . . Section 3.5 Greatest Common Divisors . . . . . . . Euclidean Rings . . . . . . . . . . . . . . . . . . Section 3.6 Unique Factorization . . . . . . . . . . . Section 3.7 Irreducibility . . . . . . . . . . . . . . . Section 3.8 Quotient Rings and Finite Fields . . . . Section 3.9 Officers, Magic, Fertilizer, and Horizons Officers . . . . . . . . . . . . . . . . . . . . . . Magic . . . . . . . . . . . . . . . . . . . . . . . Fertilizer . . . . . . . . . . . . . . . . . . . . . . Horizons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 227 232 240 250 265 272 278 288 305 305 310 314 317 Chapter 4 Linear Algebra . . . . . . . . . . . . . . . . . . . . . 321 Section 4.1 Vector Spaces . . . . . Gaussian Elimination . . . . . . Section 4.2 Euclidean Constructions Section 4.3 Linear Transformations Section 4.4 Determinants . . . . . . Section 4.5 Codes . . . . . . . . . Block Codes . . . . . . . . . . . Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 345 354 367 385 400 400 407 Chapter 5 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430 Section 5.1 Classical Formulas . . . . . . . . . Viète’s Cubic Formula . . . . . . . . . . . Section 5.2 Insolvability of the General Quintic Formulas and Solvability by Radicals . . . Translation into Group Theory . . . . . . . Section 5.3 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430 443 447 458 460 469 Chapter 6 Groups II . . . . . . . . . . . . . . . . . . . . . . . . . 473 Section 6.1 Finite Abelian Groups . . . . . . . . . . . . . . . . . . . 473 Section 6.2 The Sylow Theorems . . . . . . . . . . . . . . . . . . . 487 Section 6.3 Ornamental Symmetry . . . . . . . . . . . . . . . . . . . 498 Chapter 7 Commutative Rings II . . . . . . . . . . . . . . . . . 516 Section 7.1 Prime Ideals and Maximal Ideals . . . . . . . . . . . . . 516 Section 7.2 Unique Factorization . . . . . . . . . . . . . . . . . . . . 522 Section 7.3 Noetherian Rings . . . . . . . . . . . . . . . . . . . . . 532 C ONTENTS Section 7.4 Varieties . . . . . . . . Section 7.5 Gröbner Bases . . . . . Monomial Orders . . . . . . . . Generalized Division Algorithm Gröbner Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 538 556 557 564 569 Appendix A Inequalities . . . . . . . . . . . . . . . . . . . . . . . 581 Appendix B Pseudocodes . . . . . . . . . . . . . . . . . . . . . . 583 Hints for Selected Exercises . . . . . . . . . . . . . . . . . . . . . 587 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604 Preface to the Third Edition A First Course in Abstract Algebra introduces groups and commutative rings. Group theory was invented by E. Galois in the early 1800s, when he used groups to completely determine when the roots of polynomials can be found by formulas generalizing the quadratic formula. Nowadays, groups are the precise way to discuss various types of symmetry, both in geometry and elsewhere. Besides introducing Galois’ ideas, we also apply groups to some intricate counting problems as well as to the classification of friezes in the plane. Commutative rings provide the proper context in which to study number theory as well as many aspects of the theory of polynomials. For example, generalizations of ideas such as greatest common divisor and modular arithmetic extend effortlessly to polynomial rings over fields. Applications include public access codes, finite fields, magic squares, Latin squares, and calendars. We then consider vector spaces with scalars in arbitrary fields (not just the reals), and this study allows us to solve the classical Greek problems concerning angle trisection, doubling the cube, squaring the circle, and construction of regular ngons. Linear algebra over finite fields is applied to codes, showing how one can accurately decode messages sent over a noisy channel (for example, photographs sent to Earth from Mars or from Saturn). Here, one sees finite fields being used in an essential way. In Chapter 5, we give the classical formulas for the roots of cubic and quartic polynomials, after which both groups and commutative rings together are used to prove Galois’ theorem (polynomials whose roots are obtainable by such formulas have solvable Galois groups) and Abel’s theorem (there is no generalization of these formulas to polynomials of higher degree). This is only an introduction to Galois theory; readers wishing to learn more of this beautiful subject will have to see a more advanced text. For those readers whose appetites have been whetted by these results, the last two chapters investigate groups and rings further: we prove the basis theorem for finite abelian groups and the Sylow theorems, and we introduce the study of polynomials in several variables: varieties; Hilbert’s basis viii P REFACE TO THE T HIRD E DITION ix theorem, the Nullstellensatz, and algorithmic methods associated with Gröbner bases. Let me mention some new features of this edition. I have rewritten the text, adding more exercises, and trying to make the exposition more smooth. The following changes in format should make the book more convenient to use. Every exercise explicitly cited elsewhere in the text is marked by an asterisk; moreover, every citation gives the page number on which the cited exercise appears. Hints for certain exercises are in a section at the end of the book so that readers may consider problems on their own before reading hints. One numbering system enumerates all lemmas, theorems, propositions, corollaries, and examples, so that finding back references is easy. There are several pages of Special Notation, giving page numbers where notation is introduced. Today, abstract algebra is viewed as a challenging course; many bright students seem to have inordinate difficulty learning it. Certainly, they must learn to think in a new way. Axiomatic reasoning may be new to some; others may be more visually oriented. Some students have never written proofs; others may have once done so, but their skills have atrophied from lack of use. But none of these obstacles adequately explains the observed difficulties. After all, the same obstacles exist in beginning real analysis courses, but most students in these courses do learn the material, perhaps after some early struggling. However, the difficulty of standard algebra courses persists, whether groups are taught first, whether rings are taught first, or whether texts are changed. I believe that a major contributing factor to the difficulty in learning abstract algebra is that both groups and rings are introduced in the first course; as soon as a student begins to be comfortable with one topic, it is dropped to study the other. Furthermore, if one leaves group theory or commutative ring theory before significant applications can be given, then students are left with the false impression that the theory is either of no real value or, more likely, that it cannot be appreciated until some future indefinite time. (Imagine a beginning analysis course in which both real and complex analysis are introduced in one semester.) If algebra is taught as a oneyear (twosemester) course, there is no longer any reason to crowd both topics into the first course, and a truer, more attractive, picture of algebra is presented. This option is more practical today than in the past, for the many applications of abstract algebra have increased the numbers of interested students, many of whom are working in other disciplines. I have rewritten this text for two audiences. This new edition can serve as a text for those who wish to continue teaching the currently popular arrangement of introducing both groups and rings in the first semester. As usual, one begins by covering most of Chapter 1, after which one chooses selected parts of Chapters 2 and 3, depending on whether groups or commutative rings are taught first. Chapters 2 and 3 have been rewritten, and they are now essentially independent x P REFACE TO THE T HIRD E DITION of one another, so that this book may be used for either order of presentation. (As an aside, I disagree with the current received wisdom that doing groups first is more efficient than doing rings first; for example, the present version of Chapter 3 is about the same length as its earlier versions.) There is ample material in the book so that it can further serve as a text for a sequel course as well. Let me now address a second audience: those willing to try a new approach. My own ideas about teaching abstract algebra have changed, and I now think that a twosemester course in which only one of groups or rings is taught in the first semester, is best. I recommend a oneyear course whose first semester covers number theory and commutative rings, and whose second semester covers linear algebra and group theory. In more detail, the first semester should treat the usual selection of arithmetic theorems in Chapter 1: division algorithm; gcd’s; euclidean algorithm; unique factorization; congruence; Chinese remainder theorem. Continue with Section 2.1: functions; inverse functions; equivalence relations, and then commutative rings in Chapter 3: fraction fields of domains; generalizations of arithmetic theorems to polynomials; ideals; integers mod m; isomorphism theorems; splitting fields, existence of finite fields, magic squares, orthogonal Latin squares. One could instead continue on in Chapter 2, covering group theory instead of commutative rings, but I think that doing commutative rings first is more userfriendly. It is natural to pass from to k[x], and one can watch how the notion of ideal develops from a technique showing that gcd’s are linear combinations into an important idea. For the second semester, I recommend beginning with portions of Chapter 4: linear algebra over arbitrary fields: invariance of dimension; rulercompass constructions; matrices and linear transformations; determinants over commutative rings. Most of this material can be done quickly if the students have completed an earlier linear algebra course treating vector spaces over . If time permits, one can read the section on codes, which culminates with a proof that ReedSolomon codes can be decoded. The remainder of the semester should discuss groups, as in Chapter 2: permutations; symmetries of planar figures; Lagrange’s theorem; isomorphism theorems; group actions; Burnside counting; and frieze groups, as in Chapter 6. If there is not ample time to cover codes and frieze groups, these sections are appropriate special projects for interested students. I prefer this organization and presentation, and I believe that it is an improvement over that of standard courses. Giving the etymology of mathematical terms is rarely done. Let me explain, with an analogy, why I have included derivations of many terms. There are many variations of standard poker games and, in my poker group, the dealer announces the game of his choice by naming it. Now some names are better than others. For example, “Little Red” is a game in which one’s smallest red card is wild; this is a good name because it reminds the players of its distinctive feature. On the P REFACE TO THE T HIRD E DITION xi other hand, “Aggravation” is not such a good name, for though it is, indeed, suggestive, the name does not distinguish this particular game from several others. Most terms in mathematics have been well chosen; there are more red names than aggravating ones. An example of a good name is even permutation, for a permutation is even if it is a product of an even number of transpositions. Another example of a good term is the parallelogram law describing vector addition. But many good names, clear when they were chosen, are now obscure because their roots are either in another language or in another discipline. The trigonometric terms tangent and secant are good names for those knowing some Latin, but they are obscure otherwise (see a discussion of their etymology on page 31). The term mathematics is obscure only because most of us do not know that it comes from the classical Greek word meaning “to learn.” The term corollary is doubly obscure; it comes from the Latin word meaning “flower,” but why should some theorems be called flowers? A plausible explanation is that it was common, in ancient Rome, to give flowers as gifts, and so a corollary is a gift bequeathed by a theorem. The term theorem comes from the Greek word meaning “to watch” or “to contemplate” (theatre has the same root); it was used by Euclid with its present meaning. The term lemma comes from the Greek word meaning “taken” or “received;” it is a statement that is taken for granted (for it has already been proved) in the course of proving a theorem. I believe that etymology of terms is worthwhile (and interesting!), for it often aids understanding by removing unnecessary obscurity. In addition to thanking again those who helped me with the first two editions, it is a pleasure to thank George Bergman and Chris Heil for their valuable comments on the second edition. I also thank Iwan Duursma, Robert Friedman, Blair F. Goodlin, Dieter Koller, Fatma Irem Koprulu, J. Peter May, Leon McCulloh, Arnold Miller, Brent B. Solie, and John Wetzel. Joseph J. Rotman xii P REFACE TO THE T HIRD E DITION 1 Number Theory 1.1 I NDUCTION There are many styles of proof, and mathematical induction is one of them. We begin by saying what mathematical induction is not. In the natural sciences, inductive reasoning is the assertion that a freqently observed phenomenon will always occur. Thus, one says that the Sun will rise tomorrow morning because, from the dawn of time, the Sun has risen every morning. This is not a legitimate kind of proof in mathematics, for even though a phenomenon has been observed many times, it need not occur forever. However, inductive reasoning is still valuable in mathematics, as it is in natural science, because seeing patterns in data often helps in guessing what may be true in general. On the other hand, a reasonable guess may not be correct. For example, what is the maximum number of regions into which 3 (3dimensional space) can be divided by n planes? Two nonparallel planes can divide 3 into 4 regions, and three planes can divide 3 into 8 regions (octants). For smaller n, we note that a single plane divides 3 into 2 regions, while if n = 0, then 3 is not divided at all: there is 1 region. For n = 0, 1, 2, 3, the maximum number of regions is thus 1, 2, 4, 8, and it is natural to guess that n planes can be chosen to divide 3 into 2n regions. But it turns out that any four chosen planes can divide 3 into at most 15 regions! Before proceeding further, let us make sure that we agree on the meaning of some standard terms. An integer is one of the numbers 0, 1, −1, 2, −2, 3, . . .; the set of all the integers is denoted by (from the German Zahl meaning number): = {0, 1, −1, 2, −2, 3, . . .}. The natural numbers consists of all those integers n for which n ≥ 0: = {n in : n ≥ 0} = {0, 1, 2, 3, . . .}. 1 2 N UMBER T HEORY CH. 1 Definition. An integer d is a divisor of an integer n if n = da for some integer a. An integer n is called prime1 if n ≥ 2 and its only divisors are ±1 and ±n; an integer n is called composite if it is not prime. If a positive integer n is composite, then it has a factorization n = ab, where a < n and b < n are positive integers; the inequalities are present to eliminate the uninteresting factorization n = n × 1. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, . . .; that this sequence never ends is proved in Corollary 1.30. Consider the assertion that f (n) = n 2 − n + 41 is prime for every positive integer n. Evaluating f (n) for n = 1, 2, 3, . . . , 40 gives the numbers 41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601. It is tedious, but not very difficult, to show that every one of these numbers is prime (see Proposition 1.3). Inductive reasoning predicts that all the numbers of the form f (n) are prime. But the next number, f (41) = 1681, is not prime, for f (41) = 412 − 41 + 41 = 412 , which is obviously composite. Thus, inductive reasoning is not appropriate for mathematical proofs. Here is an even more spectacular example (which I first saw in an article by W. Sierpinski). Recall that perfect squares are numbers of the form n 2 , where n is an integer; the first few perfect squares are 0, 1, 4, 9, 16, 25, 36, . . . . For each n ≥ 1, consider the statement S(n) : 991n 2 + 1 is not a perfect square. The nth statement, S(n), is true for many n; in fact, the smallest number n for which S(n) is false is n = 12, 055, 735, 790, 331, 359, 447, 442, 538, 767 ≈ 1.2 × 1028 . The equation m 2 = 991n 2 + 1 is an example of Pell’s equation—an equation of the form m 2 = pn 2 + 1, where p is prime—and there is a way of calculating all possible solutions of it. An even larger example involves the prime 1 One reason the number 1 is not called a prime is that many theorems involving primes would otherwise be more complicated to state. I NDUCTION 3 p = 1,000,099; the smallest n for which 1,000,099n 2 + 1 is a perfect square has 1116 digits. The most generous estimate of the age of the Earth is 10 billion (10,000,000,000) years, or 3.65 × 1012 days, a number insignificant when compared to 1.2 × 1028 , let alone 101115 . If, starting from the Earth’s very first day, one verified statement S(n) on the nth day, then there would be today as much evidence of the general truth of these statements as there is that the Sun will rise tomorrow morning. And yet some of the statements S(n) are false! As a final example, let us consider the following statement, known as Goldbach’s conjecture: every even number m ≥ 4 is a sum of two primes. No one has ever found a counterexample to Goldbach’s conjecture, but neither has anyone ever proved it. At present, the conjecture has been verified for all even numbers m < 1013 , and it has been proved by J.R. Chen that every sufficiently large even number m can be written as p + q, where p is prime and q is “almost” a prime; that is, q is either a prime or a product of two primes. Even with all of this positive evidence, however, no mathematician will say that Goldbach’s conjecture must, therefore, be true for all even m. We have seen what (mathematical) induction is not; let us now discuss what induction is. Our discussion is based on the following property of the set of natural numbers (usually called the Well Ordering Principle). Least Integer Axiom. There is a smallest integer in every nonempty2 subset C of the natural numbers . Although this axiom cannot be proved (it arises in analyzing what integers are), it is certainly plausible. Consider the following procedure: check whether 0 belongs to C; if it does, then 0 is the smallest integer in C. Otherwise, check whether 1 belongs to C; if it does, then 1 is the smallest integer in C; if not, check 2. Continue this procedure until one bumps into C; this will occur eventually because C is nonempty. Proposition 1.1 (Least Criminal). Let k be a natural number, and let S(k), S(k + 1), . . . , S(n), . . . be a list of statements. If some of these statements are false, then there is a first false statement. Proof. Let C be the set of all those natural numbers n ≥ k for which S(n) is false; by hypothesis, C is a nonempty subset of . The Least Integer Axiom provides a smallest integer m in C, and S(m) is the first false statement. • This seemingly innocuous proposition is useful. Theorem 1.2. Every integer n ≥ 2 is either a prime or a product of primes. 2 Saying that C is nonempty merely means that there is at least one integer in C. 4 N UMBER T HEORY CH. 1 Proof. Were this not so, there would be “criminals:” there are integers n ≥ 2 which are neither primes nor products of primes; a least criminal m is the smallest such integer. Since m is not a prime, it is composite; there is thus a factorization m = ab with 2 ≤ a < m and 2 ≤ b < m (since a is an integer, 1 < a implies 2 ≤ a). Since m is the least criminal, both a and b are “honest,” i.e., a = pp 0 p 00 · · · and b = qq 0 q 00 · · · , where the factors p, p 0, p 00, . . . and q, q 0 , q 00 . . . . are primes. Therefore, m = ab = pp 0 p 00 · · · qq 0 q 00 · · · is a product of (at least two) primes, which is a contradiction.3 • Proposition 1.3. √If m ≥ 2 is a positive integer which is not divisible by any prime p with p ≤ m, then m is a prime. Proof. If m is not m and √ prime, then√m = ab, where a < √ √ b < m are positive integers. If a > m and b > m, then m √ = ab > m m = m, a contradiction. Therefore, we may assume that a ≤ m. By Theorem 1.2, a is either a prime or a product of primes, and any (prime) divisor p of a is also a divisor √ of m. Thus, if m is not prime, then it has a “small” prime divisor p; i.e., p ≤ m. The contrapositive says that if m has no small prime divisor, then m is prime. • Proposition 1.3 can be used to show that 991 is a prime. It suffices to check √ whether 991 is divisible by some prime p with p ≤ 991 ≈ 31.48; if 991 is not divisible by 2, 3, 5, . . . , or 31, then it is prime. There are 11 such primes, and one checks (by long division) that none of them is a divisor of 991. (One can check that 1,000,099 is a prime in the same way, but it is a longer enterprise because its square root is a bit over 1000.) It is also tedious, but not difficult, to see that the numbers f (n) = n 2 − n + 41, for 1 ≤ n ≤ 40, are all prime. Mathematical induction is a version of least criminal that is more convenient to use. The key idea is just this: Imagine a stairway to the sky. If its bottom step is white and if the next step above a white step is also white, then all the steps of the stairway must be white. (One can trace this idea back to Levi ben Gershon in 1321. There is an explicit description of induction, cited by Pascal, written by Francesco Maurolico in 1557.) For example, the statement “2n > n for all 3 The contrapositive of an implication “P implies Q” is the implication “(not Q) implies P (not P).” For example, the contrapositive of “If a series an converges, then limn→∞ an = P 0” is “If lim n→∞ an 6= 0, then an diverges.” If an implication is true, then so is its contrapositive; conversely, if the contrapositive is true, then so is the original implication. The strategy of this proof is to prove the contrapositive of the original implication. Although a statement and its contrapositive are logically equivalent, it is sometimes more convenient to prove the contrapositive. This method is also called indirect proof or proof by contradiction. I NDUCTION 5 n ≥ 1” can be regarded as an infinite sequence of statements (a stairway to the sky): 21 > 1; 22 > 2; 23 > 3; 24 > 4; 25 > 5; · · · . Certainly, 21 = 2 > 1. If 2100 > 100, then 2101 = 2 × 2100 > 2 × 100 = 100 + 100 > 101. There is nothing magic about the exponent 100; the same idea shows, having reached any stair, that we can climb up to the next one. This argument will be formalized in Proposition 1.5. Theorem 1.4 (Mathematical Induction4 ). each natural number n, suppose that: Given statements S(n), one for (i) Base Step : S(0) is true; (ii) Inductive Step : if S(n) is true, then S(n + 1) is true. Then S(n) is true for all natural numbers n. Proof. We must show that the collection C of all those natural numbers n for which the statement S(n) is false is empty. If, on the contrary, C is nonempty, then there is a first false statement S(m). Since S(0) is true, by (i), we must have m ≥ 1. This implies that m − 1 ≥ 0, and so there is a statement S(m − 1) [there is no statement S(−1)]. As m is the least criminal, m − 1 must be honest; that is, S(m − 1) is true. But now (ii) says that S(m) = S([m − 1] + 1) is true, and this is a contradiction. We conclude that C is empty and, hence, that all the statements S(n) are true. • We now show how to use induction. Proposition 1.5. 2n > n for all integers n ≥ 0. Proof. The nth statement S(n) is S(n) : 2n > n. Two steps are required for induction, corresponding to the two hypotheses in Theorem 1.4. Base step. The initial statement S(0) : 20 > 0 is true, for 20 = 1 > 0. 4 Induction, having a Latin root meaning “to lead,” came to mean “prevailing upon to do something” or “influencing.” This is an apt name here, for the nth statement influences the (n + 1)st one. 6 N UMBER T HEORY CH. 1 Inductive step. If S(n) is true, then S(n + 1) is true; that is, using the inductive hypothesis S(n), we must prove S(n + 1) : 2n+1 > n + 1. If 2n > n is true, then multiplying both sides of its inequality by 2 gives the valid5 inequality: 2n+1 = 2 × 2n > 2n. Now 2n = n + n ≥ n + 1 (because n ≥ 1), and hence 2n+1 > 2n ≥ n + 1, as desired. Having verified both the base step and the inductive step, we conclude that n 2 > n for all n ≥ 0. • Induction is plausible in the same sense that the Least Integer Axiom is plausible. Suppose that a given list S(0), S(1), S(2), . . . of statements has the property that S(n + 1) is true whenever S(n) is true. If, in addition, S(0) is true, then S(1) is true; the truth of S(1) now gives the truth of S(2); the truth of S(2) now gives the truth of S(3); and so forth. Induction replaces the phrase and so forth by the inductive step which guarantees, for every n, that there is never an obstruction in the passage from any statement S(n) to the next one, S(n + 1). Here are two comments before we give more illustrations of induction. First, one must verify both the base step and the inductive step; verification of only one of them is inadequate. For example, consider the statements S(n) : n 2 = n. The base step is true, but one cannot prove the inductive step (of course, these statements are false for all n > 1). Another example is given by the statements S(n) : n = n +1. It is easy to see that the inductive step is true: if n = n +1, then Proposition A.2 says that adding 1 to both sides gives n+1 = (n+1)+1 = n+2, which is the next statement, S(n + 1). But the base step is false (of course, all these statements are false). Second, when first seeing induction, many people suspect that the inductive step is circular reasoning: one is using S(n), and this is what one wants to prove! A closer analysis shows that this is not at all what is happening. The inductive step, by itself, does not prove that S(n + 1) is true. Rather, it says that if S(n) is true, then S(n + 1) is also true. In other words, the inductive step proves that the implication “If S(n) is true, then S(n + 1) is true” is correct. The truth of this implication is not the same thing as the truth of its conclusion. For example, consider the two statements: “Your grade on every exam is 100%” and “Your grade in the course is A.” The implication “If all your exams are perfect, then you will get the highest grade for the course” is true. Unfortunately, this does not say that it is inevitable that your grade in the course will be A. Our discussion above 5 See Proposition A.2 in Appendix A, which gives the first properties of inequalities. I NDUCTION 7 gives a mathematical example: the implication “If n = n +1, then n +1 = n +2” is true, but the conclusion “n + 1 = n + 2” is false. Remark. The Least Integer Axiom is enjoyed not only by , but also by any of its nonempty subsets Q (indeed, the proof of Proposition 1.1 uses the fact that the axiom holds for Q = {n in : n ≥ 2}). In terms of induction, this says that the base step can occur at any natural number k, not necessarily at k = 0. The conclusion, then, is that the statements S(n) are true for all n ≥ k. The Least Integer Axiom is also enjoyed by the larger set Q m = {n in : n ≥ m}, where m is any, possibly negative, integer. If C is a nonempty subset of Q m and if C ∩ {m, m + 1, . . . , −1}6 is nonempty, then this finite set contains a smallest integer, which is the smallest integer in C. If C ∩ {m, m + 1, . . . , −1} is empty, then C is actually a nonempty subset of , and the original axiom gives a smallest number in C. In terms of induction, this says that the base step can occur at any, possibly negative, integer k [assuming, of course, that there is a kth statement S(k)]. For example, if one has statements S(−1), S(0), S(1), . . . , then the base step can occur at n = −1; the conclusion in this case is that the statements S(n) are true for all n ≥ −1. Here is an induction with base step occurring at n = 1. Proposition 1.6. 1 + 2 + · · · + n = 21 n(n + 1) for every integer n ≥ 1. Proof. The proof is by induction on n ≥ 1. Base step. If n = 1, then the left side is 1 and the right side is 12 1(1+1) = 1, as desired. Inductive step. It is always a good idea to write the (n + 1)st statement S(n + 1) so one can see what has to be proved. Here, we must prove S(n + 1) : 1 + 2 + · · · + n + (n + 1) = 12 (n + 1)(n + 2). By the inductive hypothesis, i.e., using S(n), the left side is [1 + 2 + · · · + n] + (n + 1) = 21 n(n + 1) + (n + 1), and high school algebra shows that 12 n(n + 1) + (n + 1) = 21 (n + 1)(n + 2). By induction, the formula holds for all n ≥ 1. • There is a story (it probably never happened) told about Gauss as a boy. One of his teachers asked the students to add up all the numbers from 1 to 100, thereby hoping to get some time for himself for other tasks. But Gauss quickly 6 If C and D are subsets of a set X, then their intersection, denoted by C ∩ D, is the subset consisting of all those x in X lying in both C and D. 8 N UMBER T HEORY CH. 1 volunteered that the answer was 5050. He let s denote the sum of all the numbers from 1 to 100; s = 1 + 2 + · · ·+ 99 + 100. Of course, s = 100 + 99 + · · ·+ 2 + 1. Arrange these nicely: s = 1 + 2 + · · · + 99 + 100 s = 100 + 99 + · · · + 2 + 1 and add: 2s = 101 + 101 + · · · + 101 + 101, the sum 101 occurring 100 times. We now solve: s = 21 (100 × 101) = 5050. This argument is valid for any number n in place of 100 (and it does not use induction). Not only does this give a new proof of Proposition 1.6, it also shows how the formula could have been discovered.7 It is not always the case, in an inductive proof, that the base step is very simple. In fact, all possibilities can occur: both steps can be easy; both can be difficult; one is harder than the other. Proposition 1.7. If we assume ( f g)0 = f 0 g + f g 0 , the product rule for derivatives, then (x n )0 = nx n−1 for all integers n ≥ 1. Proof. We proceed by induction on n ≥ 1. Base step. If n = 1, then we ask whether (x)0 = x 0 ≡ 1, the constant function identically equal to 1. By definition, f 0 (x) = lim h→0 f (x + h) − f (x) . h When f (x) = x, therefore, (x)0 = lim h→0 x +h−x h = lim = 1. h→0 h h Inductive step. We must prove that (x n+1 )0 = (n + 1)x n . It is permissible to use the inductive hypothesis, (x n )0 = nx n−1 , as well as (x)0 ≡ 1, for the base 7 Actually, this formula goes back at least a thousand years (see Exercise 1.10 on page 13). Alhazen (Ibn alHaytham) (9651039), found a geometric way to add 1k + 2 k + · · · + n k for any fixed integer k ≥ 1 [see Exercise 1.11 on page 13]. I NDUCTION 9 step has already been proved. Since x n+1 = x n x, the product rule gives (x n+1 )0 = (x n x)0 = (x n )0 x + x n (x)0 = (nx n−1 )x + x n 1 = (n + 1)x n . We conclude that (x n )0 = nx n−1 is true for all n ≥ 1. • Here is an example of an induction whose base step occurs at n = 5. Consider the statements S(n) : 2n > n 2 . This is not true for small values of n: if n = 2 or 4, then there is equality, not inequality; if n = 3, the left side, 8, is smaller than the right side, 9. However, S(5) is true, for 32 > 25. Proposition 1.8. 2n > n 2 is true for all integers n ≥ 5. Proof. We have just checked the base step S(5). In proving S(n + 1) : 2n+1 > (n + 1)2 , we are allowed to assume that n ≥ 5 (actually, we will need only n ≥ 3 to prove the inductive step) as well as the inductive hypothesis. Multiply both sides of 2n > n 2 by 2 to get 2n+1 = 2 × 2n > 2n 2 = n 2 + n 2 = n 2 + nn. Since n ≥ 5, we have n ≥ 3, and so nn ≥ 3n = 2n + n ≥ 2n + 1. Therefore, 2n+1 > n 2 + nn ≥ n 2 + 2n + 1 = (n + 1)2 . • There is another version of induction, usually called the second form of induction, that is sometimes more convenient to use. Definition. The predecessors of a natural number n ≥ 1 are the natural numbers k with k < n, namely, 0, 1, 2, . . . , n − 1 (0 has no predecessor). Theorem 1.9 (Second Form of Induction). Let S(n) be a family of statements, one for each natural number n, and suppose that: (i) S(0) is true; (ii) if S(k) is true for all predecessors k of n, then S(n) is itself true. Then S(n) is true for all natural numbers n. 10 N UMBER T HEORY CH. 1 Proof. It suffices to show that there are no integers n for which S(n) is false; that is, the collection C of all positive integers n for which S(n) is false is empty. If, on the contrary, C is nonempty, then there is a least criminal m: there is a first false statement S(m). Since S(0) is true, by (i), we must have m ≥ 1. As m is the least criminal, k must be honest for all k < m; in other words, S(k) is true for all the predecessors of m. Then, by (ii), S(m) is true, and this is a contradiction. We conclude that C is empty and, hence, that all the statements S(n) are true. • The second form of induction can be used to give a second proof of Theorem 1.2. As with the first form, the base step need not occur at 0. Theorem 1.10 (= Theorem 1.2). product of primes. Every integer n ≥ 2 is either a prime or a Proof. 8 Base step. The statement is true when n = 2 because 2 is a prime. Inductive step. If n ≥ 2 is a prime, we are done. Otherwise, n = ab, where 2 ≤ a < n and 2 ≤ b < n. As a and b are predecessors of n, each of them is either prime or a product of primes: a = pp 0 p 00 · · · and b = qq 0 q 00 · · · , and so n = pp 0 p 00 · · · qq 0 q 00 · · · is a product of (at least two) primes. • The reason why the second form of induction is more convenient here is that it is more natural to use S(a) and S(b) than to use S(n − 1); indeed, it is not at all clear how to use S(n − 1). Here is a notational remark. We can rephrase the inductive step in the first form of induction: if S(n − 1) is true, then S(n) is true (we are still saying that if a statement is true, then so is the next statement). With this rephrasing, we can now compare the inductive steps of the two forms of induction. Each wants to prove S(n): the inductive hypothesis of the first form is S(n − 1); the inductive hypothesis of the second form is any or all of the preceding statements S(0), S(1), . . . , S(n − 1). Thus, the second form appears to have a stronger inductive hypothesis. In fact, Exercise 1.21 on page 15 asks you to prove that both forms of mathematical induction are equivalent. The next result says that one can always factor out a largest power of 2 from any integer. Proposition 1.11. Every integer n ≥ 1 has a unique factorization n = 2k m, where k ≥ 0 and m ≥ 1 is odd. 8 The similarity of the proofs of Theorems 1.2 and 1.10 indicates that the second form of induction is merely a variation of least criminal. I NDUCTION 11 Proof. We use the second form of induction on n ≥ 1 to prove the existence of k and m; the reader should see that it is more appropriate here than the first form. Base step. If n = 1, take k = 0 and m = 1. Inductive step. If n ≥ 1, then n is either odd or even. If n is odd, then take k = 0 and m = n. If n is even, then n = 2b. Because b < n, it is a predecessor of n, and so the inductive hypothesis allows us to assume S(b) : b = 2` m, where ` ≥ 0 and m is odd. The desired factorization is n = 2b = 2`+1 m. The word unique means “exactly one.” We prove uniqueness by showing that if n = 2k m = 2t m 0 , where both k and t are nonnegative and both m and m 0 are odd, then k = t and m = m 0 . We may assume that k ≥ t. If k > t, then canceling 2t from both sides gives 2k−t m = m 0 . Since k − t > 0, the left side is even while the right side is odd; this contradiction shows that k = t. We may thus cancel 2k from both sides, leaving m = m 0 . • The ancient Greeks thought that a rectangular figure is most pleasing to the eye if its edges a and b are in the proportion a : b = b : (a + b). 2 2 In this case, a(a+b) = b 2 , so that b2 −ab−a √ = 0; that is, (b/a) −b/a−1 = 0. 1 The quadratic formula gives b/a = 2 (1 ± 5). Therefore, √ √ b/a = α = 21 (1 + 5) or b/a = β = 21 (1 − 5). The number α, approximately 1.61803, is called the golden ratio. Since α is a root of x 2 − x − 1, as is β, we have α2 = α + 1 β 2 = β + 1. and The reason for discussing the golden ratio is that it is intimately related to the Fibonacci sequence. Definition. The Fibonacci sequence F0 , F1 , F2 , . . . is defined as follows: F0 = 0, F1 = 1, and Fn = Fn−1 + Fn−2 for all integers n ≥ 2. The Fibonacci sequence begins: 0, 1, 1, 2, 3, 5, 8, 13, . . . Theorem 1.12. all n ≥ 0, where α = 21 (1 + If Fn denotes the nth term of the Fibonacci sequence, then for √ Fn = √1 (α n 5 5) and β = 21 (1 − √ − β n ), 5). 12 N UMBER T HEORY CH. 1 Proof. We are going to use the second form of induction [the second form is the appropriate induction here, for the equation Fn = Fn−1 + Fn−2 suggests that proving S(n) will involve not only S(n − 1) but S(n − 2) as well]. Base step. The formula is true for n = 0 : √1 (α 0 − β 0 ) = 0 = F0 . The 5 formula is also true for n = 1: √1 (α 1 5 − β 1 ) = √1 (α − β) 5 h √ √ i 1 = √ 12 (1 + 5) − 21 (1 − 5) 5 √ 1 √ = ( 5) = 1 = F1 . 5 (We have mentioned both n = 0 and n = 1 because verifying the inductive hypothesis for Fn requires our using the truth of the statements for both Fn−1 and Fn−2 . For example, knowing only that F2 = √1 (α 2 − β 2 ) is not enough to 5 prove that the formula for F3 is true; one also needs the formula for F1 .) Inductive step. If n ≥ 2, then Fn = Fn−1 + Fn−2 = √1 (α n−1 5 = 5 1 √ (α n 5 − β n−1 ) + √1 (α n−2 5 − β n−2 ) h i = √1 (α n−1 + α n−2 ) − (β n−1 + β n−2 ) 5 h i 1 = √ α n−2 (α + 1) − β n−2 (β + 1) 5 h i 1 = √ α n−2 (α 2 ) − β n−2 (β 2 ) − β n ), because α + 1 = α 2 and β + 1 = β 2 . • ber It is curious that the integers Fn are expressed in terms of the irrational num√ 5. Corollary 1.13. If α = Remark. 1 2 1+ √ 5 , then Fn > α n−2 for all integers n ≥ 3. If n = 2, then F2 = 1 = α 0 , and so there is equality, not inequality. Proof. Base step. If n = 3, then F3 = 2 > α, for α ≈ 1.618. Inductive step. We must show that Fn+1 > α n−1 . By the inductive hypothesis, Fn+1 = Fn + Fn−1 > α n−2 + α n−3 = α n−3 (α + 1) = α n−3 α 2 = α n−1 . • I NDUCTION 13 One can also use induction to give definitions. For example, we can define n factorial,9 denoted by n!, by induction on n ≥ 0. Define 0! = 1, and if n! is known, then define (n + 1)! = n!(n + 1). One reason for defining 0! = 1 will be apparent in the next section. E XERCISES 1.1 Find a formula for 1 + 3 + 5 + · · · + (2n − 1), and use mathematical induction to prove that your formula is correct. (Inductive reasoning is used in mathematics to help guess what might be true. Once a guess has been made, it must still be proved, perhaps using mathematical P induction, perhaps by some other method.) 1.2 Find a formula for 1 + nj =1 j ! j , and use induction to prove that your formula is correct. *1.3 (i) For any n ≥ 0 and any r 6= 1, prove that 1 + r + r 2 + r 3 + · · · + r n = (1 − r n+1 )/(1 − r ). (ii) Prove that 1 + 2 + 22 + · · · + 2n = 2n+1 − 1. Show, for all n ≥ 1, that 10n leaves remainder 1 after dividing by 9. Prove that if 0 ≤ a ≤ b, then a n ≤ bn for all n ≥ 0. Prove that 12 + 22 + · · · + n 2 = 61 n(n + 1)(2n + 1) = 13 n 3 + 21 n 2 + 61 n. Prove that 13 + 23 + · · · + n 3 = 41 n 4 + 21 n 3 + 41 n 2 . 1 n. Prove that 14 + 24 + · · · + n 4 = 15 n 5 + 21 n 4 + 31 n 3 − 30 (M. Barr) There is a famous anecdote describing a hospital visit of G. H. Hardy to Ramanujan. Hardy mentioned that the number 1729 of the taxi he had taken to the hospital was not an interesting number. Ramanujan disagreed, saying that it is the smallest positive integer that can be written as the sum of two cubes in two different ways. (i) Prove that Ramanujan’s statement is true. (ii) Prove that Ramanujan’s statement is false. P *1.10 Derive the formula for ni=1 i by computing the area (n + 1)2 of a square with sides of length n + 1 using Figure P1.1. *1.11 (i) Derive the formula for ni=1 i by computing the area n(n + 1) of a rectangle with height n + 1 and base n, as pictured in Figure 1.2. (ii) (Alhazen) For fixed k ≥ 1, use Figure 1.3 to prove 1.4 1.5 1.6 1.7 1.8 1.9 (n + 1) n X i=1 ik = n X i=1 i k+1 + n X i X i=1 p=1 pk . 9 The term factor comes from the Latin “to make” or “to contribute”; the term factorial recalls that n! has many factors. 14 N UMBER T HEORY 5 1 1 1 1 4 1 1 1 1 3 1 1 1 2 1 1 1 1 CH. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Figure 1.1 1 + 2 + · · · + n = 12 (n 2 − n) Figure 1.2 1 + 2 + · · · + n = 12 n(n − 1) k k + 3k + 4k k k + 3k + 4k k k + k k 1 + 2 1 + 2 1 + 2 1 + 2 1k 1k+1 1k 2 2 3k k 5 k 3k 3 k+1 k+1 + Figure 1.3 4 k+1 4k 5 k+1 5 k Alhazan’s Dissection P (iii) Given the formula ni=1 i = 12 n(n +1), use part (ii) to derive the formula Pn 2 for i=1 i . 1.12 (i) Prove that 2n > n 3 for all n ≥ 10. (ii) Prove that 2n > n 4 for all n ≥ 17. (iii) If k is a natural number, prove that 2n > n k for all n ≥ k 2 + 1. P n 1.13 Around 1350, N. Oresme was able to sum the series ∞ n=1 n/2 by dissecting the region R in Figure 1.4 in two ways. Let A n be the vertical rectangle with base 21n and height n, so that area( A n ) = n/2n , and let rectangle with P Bn be horizontal 1 n base 21n + 2n+1 + · · · and height 1. Prove that ∞ n=1 n/2 = 2. *1.14 Let g1 (x), . . . , gn (x) be differentiable functions, and let f (x) be their product: f (x) = g1 (x) · · · gn (x). Prove, for all integers n ≥ 2, that the derivative f 0 (x) = n X i=1 g1 (x) · · · gi−1 (x)gi0 (x)gi+1 (x) · · · gn (x). I NDUCTION B3 B2 B1 1 A1 A2 A3 1 2 1 4 1 8 B0 Figure 1.4 15 1 1 1 1 Oresme’s Dissections 1.15 Prove, for every n ∈ , that (1 + x)n ≥ 1 + nx whenever x ∈ and 1 + x > 0. 1.16 Prove that every positive integer a has a unique factorization a = 3 k m, where k ≥ 0 and m is not a multiple of 3. 1.17 Prove that Fn < 2n for all n ≥ 0, where F0 , F1 , F2 , . . . is the Fibonacci sequence. 1.18 If Fn denotes the nth term of the Fibonacci sequence, prove that m X n=1 Fn = Fm+2 − 1. 1.19 Prove that 4n+1 + 52n−1 is divisible by 21 for all n ≥ 1. 1.20 For any integer n ≥ 2, prove that there are n consecutive composite numbers. Conclude that the gap between consecutive primes can be arbitrarily large. *1.21 Prove that the first and second forms of mathematical induction are equivalent; that is, prove that Theorem 1.4 is true if and only if Theorem 1.9 is true. *1.22 (Double Induction) Let S(m, n) be a doubly indexed family of statements, one for each m ≥ 0 and n ≥ 0. Suppose that (i) S(0, 0) is true; (ii) if S(m, 0) is true, then S(m + 1, 0) is true; (iii) if S(m, n) is true for all m, then S(m, n + 1) is true for all m. Prove that S(m, n) is true for all m ≥ 0 and n ≥ 0. 1.23 Use double induction to prove that (m + 1)n > mn for all m, n ≥ 0. 16 N UMBER T HEORY CH. 1 1.2 B INOMIAL C OEFFICIENTS What is the pattern of the coefficients in the formulas for the powers (1 + x) n of the binomial 1 + x? The first few such formulas are: (1 + x)0 = 1 (1 + x)1 = 1 + 1x (1 + x)2 = 1 + 2x + 1x 2 (1 + x)3 = 1 + 3x + 3x 2 + 1x 3 (1 + x)4 = 1 + 4x + 6x 2 + 4x 3 + 1x 4 . Figure 1.5, called Pascal’s triangle, after B. Pascal (1623–1662), displays an arrangement of the first few coefficients. Figure 1.6, a picture from China in 1 1 1 1 1 1 1 1 7 2 3 4 5 6 1 3 6 10 15 21 1 4 10 20 35 1 1 5 15 35 1 6 21 1 7 1 Figure 1.5 the year 1303, shows that the pattern of coefficients had been recognized long before Pascal was born. The expansion of (1 + x)n is an expression of the form c0 + c1 x + c 2 x 2 + · · · + c n x n . The coefficients cr are called binomial coefficients.10 L. Euler (1707–1783) 10 Binomial, coming from the Latin bi, meaning “two,” and nomen, meaning “name” or “term,” describes expressions of the form a + b. Similarly, trinomial describes expressions of the form a + b + c, and monomial describes expressions with a single term. The word is used here because the binomial coefficients arise when expanding powers of the binomial 1 + x. The word polynomial is a hybrid, coming from the Greek poly meaning “many” and the Latin nomen; polynomials are certain expressions having many terms. B INOMIAL C OEFFICIENTS Figure 1.6 Pascal’s Triangle, China, ca. 1300 17 18 N UMBER T HEORY CH. 1 n introduced the notation nr for them; this symbol evolved into r , which is generally accepted nowadays: n = coefficient cr of x r in (1 + x)n . r Hence, n (1 + x) = n n X n r=0 r xr . The number r is pronounced “n choose r ” because it also arises in counting problems, as we shall see later in this section. Observe, in Figure 1.5, that an inside number (i.e., not a 1 on the border) of the (n + 1)th row can be computed by going up to the nth row and adding the two neighboring numbers above it. For example, the inside numbers in row 4 1 1 3 4 3 6 1 4 1 be computed from row 3 as follows: 4 = 1 + 3, 6 = 3 + 3, and 4 = 3 + 1. Let us prove that this observation always holds. Lemma 1.14. For all integers n ≥ 1 and all r with 0 < r < n + 1, n n n+1 . + = r r −1 r Proof. We must show, for all n ≥ 1, that if (1 + x)n = c0 + c1 x + c2 x 2 + · · · + cn x n , then the coefficient of x r in (1 + x)n+1 is cr−1 + cr . Since c0 = 1, (1 + x)n+1 = (1 + x)(1 + x)n = (1 + x)n + x(1 + x)n = (c0 + c1 x + c2 x 2 + · · · + cn x n ) + x(c0 + c1 x + c2 x 2 + · · · + cn x n ) = (c0 + c1 x + c2 x 2 + · · · + cn x n ) + c0 x + c1 x 2 + c2 x 3 + · · · + cn x n+1 = 1 + (c0 + c1 )x + (c1 + c2 )x 2 + (c2 + c3 )x 3 + · · · . B INOMIAL C OEFFICIENTS Thus n+1 r , 19 the coefficient of x r in (1 + x)n+1 , is n n cr−1 + cr = + . • r −1 r Proposition 1.15 (Pascal). For all n ≥ 0 and all r with 0 ≤ r ≤ n, n! n = . r !(n − r )! r Proof. We prove the proposition by induction on n ≥ 0. Base step.11 If n = 0, then 0 = 0!/0!0! = 1. 0 Inductive step. Assuming the formula for nr for all r , we must prove (n + 1)! n+1 = . r r !(n + 1 − r )! If r = 0, then n+1 = 1 = (n + 1)!/0!(n + 1 − 0)!; if r = n + 1, then 0 n+1 n+1 = 1 = (n + 1)!/(n + 1)!0!; if 0 < r < n + 1, we use Lemma 1.14: n+1 n n = + r r −1 r n! n! = + (r − 1)!(n − r + 1)! r !(n − r )! 1 n! 1 + = (r − 1)!(n − r )! (n − r + 1) r r + n − r + 1 n! = (r − 1)!(n − r )! r (n − r + 1) n! n+1 = (r − 1)!(n − r )! r (n − r + 1) (n + 1)! = . • r !(n + 1 − r )! Corollary 1.16. For any real number x and for all integers n ≥ 0, n n X n r X n! n xr . (1 + x) = x = r !(n − r )! r r=0 11 This is one reason why 0! is defined to be 1. r=0 20 N UMBER T HEORY CH. 1 Proof. The first equation is the definition of the binomial coefficients, and the n second equation replaces r by the value given in Pascal’s theorem. • Corollary 1.17 (Binomial Theorem). For all real numbers a and b and for all integers n ≥ 1, n n X n! n n−r r X a b = (a + b)n = a n−r br . r r !(n − r )! r=0 r=0 Proof. The result is trivially true when a = 0 (if we agree that 00 = 1). If a 6 = 0, set x = b/a in Corollary 1.16, and observe that (a + b)n b n a + b n = = . 1+ a a an Therefore, n n r X X b n n n−r r n b n n n (a + b) = a 1 + a b . • = =a r r a r a r=0 r=0 Remark. The binomial theorem can be proved without first proving Corollary 1.16; just prove the formula for (a + b)n by induction on n ≥ 0. We have chosen the proof above for clearer exposition. Here is a combinatorial interpretation of the binomial coefficients. Given a set X , an rsubset is a subset of X with exactly r elements. If X has n elements, denote the number of its r subsets by [n, r ]; that is, [n, r ] is the number of ways one can choose r things from a box of n things. We compute [n, r ] by considering a related question. Given an “alphabet” with n (distinct) letters and a number r with 1 ≤ r ≤ n, an ranagram is a sequence of r of these letters with no repetitions. For example, the 2anagrams on the alphabet a, b, c are ab, ba, ac, ca, bc, cb (note that aa, bb, cc are not on this list). How many r anagrams are there on an alphabet with n letters? We count the number of such anagrams in two ways. (1) There are n choices for the first letter; since no letter is repeated, there are only n − 1 choices for the second letter, only n − 2 choices for the third letter, and so forth. Thus, the number of r anagrams is n(n − 1)(n − 2) · · · (n − [r − 1]) = n(n − 1)(n − 2) · · · (n − r + 1). B INOMIAL C OEFFICIENTS 21 Note the special case n = r : the number of nanagrams on n letters is n!. (2) Here is a second way to count these anagrams. First choose an r subset of the alphabet (consisting of r letters); there are [n, r ] ways to do this, for this is exactly what the symbol [n, r ] means. For each chosen r subset, there are r ! ways to arrange the r letters in it (this is the special case of our first count when n = r ). The number of r anagrams is thus r ![n, r ]. We conclude that r ![n, r ] = n(n − 1)(n − 2) · · · (n − r + 1), from which it follows, by Pascal’s formula, that [n, r ] = n(n − 1)(n − 2) · · · (n − r + 1)/r ! = n n . r This is why the binomial coefficient r is often pronounced as “n choose r .” As an example, how many ways are there to choose 2 hats from a closet containing 14 different hats? (One of my friends does not like the phrasing of this question. After all, one can choose 2 hats with one’s left hand, with one’s right hand, with one’s teeth, . . . ; but I continue the evil tradition.) The answer is 14 2 , and Pascal’s formula allows us to compute this as (14 × 13)/2 = 91. n Our first interpretation of the binomial coefficients r was algebraic; that is, as coefficients of polynomials which can be calculated by Pascal’s formula; our second interpretation is combinatorial; that is, as n choose r . Quite often, each interpretation can be used to prove a desired result. For example, here is a combinatorial proof of Lemma 1.14. Let X be a set with n + 1 elements, and n+1 let us color one of its elements red and the other n elements blue. Now r is the number of r subsets of X . There are two possibilities for an r subset Y : either it contains the red element or it is all blue. If Y contains the red element, then Y consists of the red element and r − 1 blue elements, and so the number of n such Y is the same as the number of all blue (r − 1)subsets, namely, r −1 . The n other possibility is that Y is all blue, and there are r such r subsets. Therefore, n+1 n n = r −1 + r , as desired. r We are now going to apply the binomial theorem to trigonometry, but we begin by reviewing properties of the complex numbers. Recall that the modulus z of a complex number z = a + i b is defined to be p z = a 2 + b2 . If we identify a complex number z = a + i b with the point (a, b) in the plane, then its modulus z is the distance from z to the origin. It follows that every 22 N UMBER T HEORY CH. 1 complex number z of modulus 1 corresponds to a point on the unit circle, and so it has coordinates (cos θ, sin θ ) for some angle θ (in the right triangle O P A in Figure 1.7, we have cos θ = O A/O P = O A, because O P = 1, and sin θ = P A/O P = P A). z = (a, b) P = (cos , sin ) r = z O Figure 1.7 A (1, 0) (a, b) = r (cos θ + i sin θ ) Proposition 1.18 (Polar Decomposition). Every complex number z has a factorization z = r (cos θ + i sin θ ), where r = z ≥ 0 and 0 ≤ θ < 2π. Proof. If z = 0, then z = 0 and any choice of θ works. If z = a +bi 6 = 0, then z 6 = 0. Now z/z = a/z + i b/z has modulus 1, for (a/z)2 + (b/z)2 = (a 2 + b2 )/z2 = 1. Therefore, there is an angle θ with z = cos θ + i sin θ, z and so z = z(cos θ + i sin θ ) = r (cos θ + i sin θ ). • If z = a + i b = r (cos θ + i sin θ ), then (r, θ ) are the polar coordinates12 of z; this is the reason Proposition 1.18 is called the polar decomposition of z. The trigonometric addition formulas for cos(θ + ψ) and sin(θ + ψ) have a lovely translation in the language of complex numbers. 12 A pole is an axis about which rotation occurs. For example, the axis of the Earth has endpoints the North and South Poles. Here, we take the pole to be the zaxis (perpendicular to the plane). B INOMIAL C OEFFICIENTS 23 Proposition 1.19 (Addition Theorem). If z = cos θ + i sin θ and w = cos ψ + i sin ψ, then zw = cos(θ + ψ) + i sin(θ + ψ). Proof. zw = (cos θ + i sin θ )(cos ψ + i sin ψ) = (cos θ cos ψ − sin θ sin ψ) + i (sin θ cos ψ + cos θ sin ψ). The trigonometric addition formulas show that zw = cos(θ + ψ) + i sin(θ + ψ). • The addition theorem gives a geometric interpretation of complex multiplication: if z = r (cos θ + i sin θ ) and w = s(cos ψ + i sin ψ), then zw = r s[cos(θ + ψ) + i sin(θ + ψ)], and the polar coordinates of zw are (r s, θ + ψ). Corollary 1.20. If z and w are complex numbers, then zw = z w. Proof. If the polar decompositions of z and w are z = r (cos θ + i sin θ ) and w = s(cos ψ +i sin ψ), respectively, then we have just seen that z = r , w = s, and zw = r s. • It follows from this corollary that if z and w lie on the unit circle, then their product zw also lies on the unit circle. In 1707, A. De Moivre (1667–1754) proved the following elegant result. Theorem 1.21 (De Moivre). For every real number x and every positive integer n, cos(nx) + i sin(nx) = (cos x + i sin x)n . 24 N UMBER T HEORY CH. 1 Proof. We prove De Moivre’s theorem by induction on n ≥ 1. The base step n = 1 is obviously true. For the inductive step, (cos x + i sin x)n+1 = (cos x + i sin x)n (cos x + i sin x) = [cos(nx) + i sin(nx)](cos x + i sin x) (inductive hypothesis) = cos(nx + x) + i sin(nx + x) (addition formula) = cos([n + 1]x) + i sin([n + 1]x). • Example 1.22. Let us find the value of (cos 3◦ + i sin 3◦ )40 . By De Moivre’s theorem, (cos 3◦ + i sin 3◦ )40 = cos 120◦ + i sin 120◦ = − 21 + i √ 3 2 . Here are the double and triple angle formulas. Corollary 1.23. (i) (ii) cos(2x) = cos2 x − sin2 x = 2 cos2 x − 1 sin(2x) = 2 sin x cos x. cos(3x) = cos3 x − 3 cos x sin2 x = 4 cos3 x − 3 cos x sin(3x) = 3 cos2 x sin x − sin3 x = 3 sin x − 4 sin3 x. Proof. (i) cos(2x) + i sin(2x) = (cos x + i sin x)2 = cos2 x + 2i sin x cos x + i 2 sin2 x = cos2 x − sin2 x + i (2 sin x cos x). Equating real and imaginary parts gives both double angle formulas. (ii) De Moivre’s theorem gives cos(3x) + i sin(3x) = (cos x + i sin x)3 = cos3 x + 3i cos2 x sin x + 3i 2 cos x sin2 x + i 3 sin3 x = cos3 x − 3 cos x sin2 x + i (3 cos2 x sin x − sin3 x). Equality of the real parts gives cos(3x) = cos3 x − 3 cos x sin2 x; the second formula for cos(3x) follows by replacing sin2 x by 1 − cos2 x. Equality of the imaginary parts gives sin(3x) = 3 cos2 x sin x − sin3 x = 3 sin x − 4 sin3 x; the second formula arises by replacing cos2 x by 1 − sin2 x. • B INOMIAL C OEFFICIENTS 25 Corollary 1.23 will be generalized in Proposition 1.24. If f 2 (x) = 2x 2 − 1, then cos(2x) = 2 cos2 x − 1 = f 2 (cos x), and if f 3 (x) = 4x 3 − 3x, then cos(3x) = 4 cos3 x − 3 cos x = f 3 (cos x). Proposition 1.24. For all n ≥ 1, there is a polynomial f n (x) having all coefficients integers such that cos(nx) = f n (cos x). Proof. By De Moivre’s theorem, cos(nx) + i sin(nx) = (cos x + i sin x)n n X n (cos x)n−r (i sin x)r . = r r=0 The real part of the left side, cos(nx), must be equal to the real part of the right side. Now i r is real if and only if13 r is even, and so n X n (cos x)n−r (i sin x)r . cos(nx) = r r even If r = 2k, then i r = i 2k = (−1)k , and cos(nx) = bn/2c X k=0 (−1) k n (cos x)n−2k sin2k x 2k (bn/2c denotes the largest integer m with m ≤ n/2).14 But sin2k x = (sin2 x)k = (1 − cos2 x)k , which is a polynomial in cos x. This completes the proof. • It is not difficult to show that f n (x) begins with 2n−1 x n . A sine version of Proposition 1.24 can be found in Exercise 1.31 on page 33. 13 The converse of an implication “If P is true, then Q is true” is the implication “If Q is true, then P is true.” An implication may be true without its converse being true. For example, “If a = b, then a 2 = b2 .” The phrase if and only if means that both the statement and its converse are true. 14 bxc, called the floor of x or the greatest integer in x, is the largest integer m with m ≤ x. For example, b3c = 3 and bπc = 3. 26 N UMBER T HEORY CH. 1 We are now going to present a beautiful formula discovered by Euler, but we begin by recalling some power series formulas from calculus to see how it arises. For every real number x, ex = 1 + x + cos x = 1 − xn x2 +··· + + ··· , 2! n! x2 x4 (−1)n x 2n + − ···+ + ··· , 2! 4! (2n)! and x3 x5 (−1)n x 2n+1 + − ···+ +··· . 3! 5! (2n + 1)! P n One can define convergence of any power series ∞ n=0 cn z , where z and cn are complex numbers, and one can show that the series sin x = x − 1+z+ zn z2 +···+ +··· 2! n! converges for every complex number z; the complex exponential e z is defined to be the sum of this series. Euler’s Theorem. For all real numbers x, ei x = cos x + i sin x. Proof. (Sketch) Now ei x = 1 + i x + (i x)2 (i x)n +···+ + ··· . 2! n! As n varies over 0, 1, 2, 3, . . ., the powers of i repeat every four steps: that is, i n takes values 1, i, −1, −i, 1, i, −1, −i, 1, . . . . Thus, the even powers of i x do not involve i , whereas the odd powers do. Collecting terms, one has e i x = even terms + odd terms, where even terms = 1 + = 1− (i x)2 (i x)4 + + ··· 2! 4! x2 x4 + − · · · = cos x 2! 4! B INOMIAL C OEFFICIENTS 27 and odd terms = i x + (i x)3 (i x)5 + +··· . 3! 5! x3 x5 = i x− + − · · · = i sin x. 3! 5! Therefore, ei x = cos x + i sin x. • It is said that Euler was especially pleased with the equation eπ i = −1; indeed, this formula is inscribed on his tombstone. As a consequence of Euler’s theorem, the polar decomposition can be rewritten in exponential form: Every complex number z has a factorization z = r eiθ , where r ≥ 0 and 0 ≤ θ < 2π . The addition theorem and De Moivre’s theorem can be restated in complex exponential form. The first becomes ei x eiy = ei(x+y) ; the second becomes (ei x )n = einx . Definition. If n ≥ 1 is an integer, then an nth root of unity is a complex number ζ with ζ n = 1. Corollary 1.25. Every nth root of unity ζ is equal to e2π ik/n = cos(2π k/n) + i sin(2π k/n), for some k with 0 ≤ k ≤ n − 1. Proof. If ζ = cos(2π/n) + i sin(2π/n), then De Moivre’s theorem, Theorem 1.21, gives ζ n = [cos(2π/n) + i sin(2π/n)]n = cos(n2π/n) + i sin(n2π/n) = cos(2π ) + i sin(2π ) = 1, 28 N UMBER T HEORY CH. 1 so that ζ is an nth root of unity. Finally, if k is an integer, then ζ n = 1 implies (ζ k )n = (ζ n )k = 1k = 1, and so ζ k = cos(2π k/n) + i sin(2π k/n) is also an nth root of unity. Conversely, assume that ζ is an nth root of unity. By the polar decomposition, Proposition 1.18, we have ζ = cos θ + i sin θ (because ζ  = 1). By De Moivre’s theorem, 1 = ζ n = cos nθ + i sin nθ . Since cos θ = 1 if and only if θ = 2kπ for some integer k, we have nθ = 2kπ ; that is, ζ = cos(2kπ/n) + i sin(2kπ/n). It is clear that we may choose k so that 0 ≤ k < n because cos x is periodic with period 2π . • Corollary 1.20 states that zw = z w for any complex numbers z and w. It follows that if ζ is an nth root of unity, then 1 = ζ n  = ζ n , so that ζ  = 1 and ζ lies on the unit circle. Given a positive integer n, let θ = 2π/n and let ζ = eiθ . The polar coordinates of ζ are (1, θ ), the polar coordinates of ζ 2 are (1, 2θ ), the polar coordinates of ζ 3 are (1, 3θ ),. . . , the polar coordinates of ζ n−1 are (1, (n − 1)θ ), and the polar coordinates of ζ n = 1 are (1, nθ ) = (1, 0). Thus, the nth roots of unity are evenly spaced around the unit circle. Figure 1.8 shows the 8th roots of unity (here, θ = 2π/8 = π/4). i √ 1 2 √ 2 (1 + i) (−1 + i) 1 −1 1 √ 2 (−1 − i) √ 2 (1 − i) 1 Figure 1.8 1 −i 8th Roots of Unity √ √ Just as there are two square roots of a number a, namely, a and − a, there √ are n different nth roots of a, namely, e 2π ik/n n a for k = 0, 1, . . . , n − 1. For example, the cube roots of unity are 1, ζ = cos 120◦ + i sin 120◦ = − 21 + i and √ 3 2 √ ζ 2 = cos 240◦ + i sin 240◦ = − 21 − i 23 . √ √ √ 3 3 3 There are 3 cube roots of 2, namely, 2, ζ 2, and ζ 2 2. B INOMIAL C OEFFICIENTS 29 Every nth root of unity is, of course, a root of the polynomial x n − 1. Therefore, Y (x − ζ ). xn − 1 = ζ n =1 If ζ is an nth root of unity, and if n is the smallest positive integer for which ζ n = 1, we say that ζ is a primitive n th root of unity. For example, ζ = e 2π i/n is a primitive nth root of unity. Now i is an 8th root of unity, for i 8 = 1; it is not a primitive 8th root of unity, but it is a primitive 4th root of unity. Lemma 1.26. Let ζ be a primitive dth root of unity. If ζ n = 1, then d must be a divisor of n. Proof. By long division, n/d = q + r/d, where q and r are natural numbers and 0 ≤ r/d < 1; that is, n = qd + r , where 0 ≤ r < d. But 1 = ζ n = ζ qd+r = ζ qd ζ r = ζ r , because ζ qd = (ζ d )q = 1. If r 6 = 0, we contradict d being the smallest exponent for which ζ d = 1. Hence, n = qd, as claimed. • Definition. defined by If d is a positive integer, then the dth cyclotomic15 polynomial is 8d (x) = Y (x − ζ ), where ζ ranges over all the primitive dth roots of unity. In Proposition 3.47, we will prove that all the coefficients of 8d (x) are integers. The following result is almost obvious. Proposition 1.27. For every integer n ≥ 1, Y 8d (x), xn − 1 = dn where d ranges over all the positive divisors d of n [in particular, 81 (x) and 8n (x) occur]. 15 The roots of x n − 1 are the nth roots of unity: 1, ζ, ζ 2 , . . . , ζ n−1 , where ζ = e2πi/n = cos(2π/n) +i sin(2π/n). Now these roots divide the unit circle {ζ ∈ : z = 1} into n equal arcs (see Figure 1.8). This explains the term cyclotomic, for its Greek origin means “circle splitting.” 30 N UMBER T HEORY CH. 1 Proof. In light of Corollary 1.25, the proposition follows by collecting, for each Q n divisor d of n, all terms in the equation x − 1 = (x − ζ ) with ζ a primitive dth root of unity. • For example, if p is a prime, then x p − 1 = 81 (x)8 p (x). Since 81 (x) = x − 1, it follows that 8 p (x) = x p−1 + x p−2 + · · · + x + 1. Definition. mial: The Euler φfunction is the degree of the nth cyclotomic polynoφ(n) = deg(8n (x)). In Proposition 1.39, we will give another description of the Euler φfunction that does not depend on roots of unity. Corollary 1.28. For every integer n ≥ 1, we have X n= φ(d). dn Proof. Note that φ(n) is the degree of 8n (x), and use the fact that the degree of a product of polynomials is the sum of the degrees of the factors. • Where do the names of the trigonometric functions come from? The cir A B 1 O C D E Figure 1.9 Etymology of Trigonometric Names cle in Figure 1.9 is the unit circle, and so the coordinates of the point A are (cos α, sin α); that is, O D = cos α and  A D = sin α. The reader may show B INOMIAL C OEFFICIENTS 31 that BC = tan α (the Latin word tangere means “to touch,” and a tangent is a line which touches the circle in only one point), and that O B = sec α (the Latin word secare means “to cut,” and a secant is a line that cuts a circle). The complement of an acute angle α is 90◦ − α, and so the name cosine arises from that of sine because of the identity cos α = sin(90◦ − α). The reason for the term sine is more amusing. We see in Figure 1.9 that sin α =  A D = 21  AE; that is, sin α is half the length of the chord AE. The fifth century Indian mathematician Aryabhata called the sine ardhajya (half chord) in Sanskrit, which was later abbreviated to jya. A few centuries later, books in Arabic transliterated jya as jiba. In Arabic script, there are letters and diacritical marks; roughly speaking, the letters correspond to our consonants, while the diacritical marks correspond to our vowels. It is customary to suppress diacritical marks in writing; for example, the Arabic version of jiba is written jb (using Arabic characters, of course). Now jiba, having no other meaning in Arabic, eventually evolved into jaib, which is an Arabic word, meaning “bosom of a dress” (a fine word, but having absolutely nothing to do with halfchord). Finally, Gherardo of Cremona, ca. 1150, translated jaib into its Latin equivalent, sinus. And this is why sine is so called, for sinus means bosom! As long as we are discussing etymology, why is a root so called? Just as the Greeks called the bottom side of a triangle its base (as in the area formula 1 2 altitude × base), they also called the bottom side of a square its base. A natural question for the Greeks was: Given a square of area A, what is the √ √ length of its side? Of course, the answer is A. Were we inventing a word for A, we might have called it the base of A or the side of A. Similarly, consider the analogous threedimensional question: given a cube of volume V , what is the √ length of its √ edge? The answer 3 V might be called the cube base of V , and A might then be called the square base of A. Why, then, do we call these numbers cube root and square root? What has any of this to do with plants? Since tracing the etymology of words is not a simple matter, we only suggest the following explanation. Through about the fourth and fifth centuries, most mathematics was written in Greek, but, by the fifth century, India had become a center of mathematics, and important mathematical texts were also written in Sanskrit. The Sanskrit term for square root is pada. Both Sanskrit and Greek are IndoEuropean languages, and the Sanskrit word pada is a cognate of the Greek word podos; both mean base in the sense of the foot of a pillar or, as above, the bottom of a square. In both languages, however, there is a secondary meaning: the root of a plant. In translating from Sanskrit, Arab mathematicians chose the secondary meaning, perhaps in error (Arabic is not an IndoEuropean language), perhaps for some unknown reason. For example, the influential book by al 32 N UMBER T HEORY CH. 1 Khwarizmi, Aljabr w’al muqabala,16 which appeared in the year 830, used the Arabic word jidhr, meaning root of a plant. (The word algebra is a European version of the first word in the title of this book; the author’s name has also come into the English language as the word algorithm.) This mistranslation has since been handed down through the centuries; the term jidhr became standard in Arabic mathematical writings, and European translations from Arabic into Latin used √ the word radix (meaning root, as in radish or radical). The notation r 2 for 2 occurs in European writings from about the twelfth century (but the square root symbol did not arise from the letter r ; it evolved from an old dot notation). However, there was a competing notation in use at the √ same time, for some scholars who translated directly from the Greek denoted 2 by l2, where l abbreviates the Latin word latus, meaning side. Finally, with the invention of logarithms in the 1500s, r won out over l, for the notation l2 was then commonly used to denote log 2. The passage from square root to cube root to the root of a polynomial equation other than x 2 − a and x 3 − a is a natural enough generalization. Thus, as pleasant as it would be, there seems to be no botanical connection with roots of equations. E XERCISES 1.24 Prove that the binomial theorem holds for complex numbers: if u and v are complex numbers, then n X n n−r r n (u + v) = u v . r r=0 *1.25 Show that the binomial coefficients are “symmetric”: n n = r n −r for all r with 0 ≤ r ≤ n. *1.26 Show, for every n, that the sum of the binomial coefficients is 2n : n n n n + + + ··· + = 2n . 0 1 2 n 1.27 (i) Show, for every n ≥ 1, that the “alternating sum” of the binomial coefficients is zero: n n n n n − + − · · · + (−1) = 0. 0 1 2 n 16 One can translate this title from Arabic, but the words already had a technical meaning: both jabr and muqabala refer to certain operations akin to subtracting the same number from both sides of an equation. B INOMIAL C OEFFICIENTS 33 (ii) Use part (i) to prove, for a given n, that the sum of all the binomial con n efficients r with r even is equal to the sum of all those r with r odd. 1.28 Prove that if n ≥ 2, then n X n = 0. (−1)r−1 r r r=1 *1.29 If 0 ≤ r ≤ n, prove that n n n−1 = . r r r −1 1.30 Let ε1 , . . . , εn be complex numbers with ε j  = 1 for all j , where n ≥ 2. (i) Prove that n n X X ε j = n. εj ≤ j =1 j =1 (ii) Prove that there is equality, n X j =1 ε j = n, if and only if all the ε j are equal. *1.31 For all odd n ≥ 1, prove that there is a polynomial gn (x), all of whose coefficients are integers, such that sin(nx) = gn (sin x). 1.32 (Star of David) Prove, for all n > r ≥ 1, that n−1 n n+1 n−1 n n+1 = . r −1 r +1 r r r −1 r +1 n−1 n−1 UUUU UUUUiiiiiii r iii UUUUUU i UUUU iii i i i UUUU ii i i UUU i i n ii n U UUUU i r−1 r UUUU iiii UUUU iiii i i i UUUU iiii Ui iiiiUUUUUUU i ii i r−1 n+1 r n r+1 n+1 r+1 What is the coefficient of x16 in (1 + x)20 ? How many ways are there to choose 4 colors from a palette containing paints of 20 different colors? 1.34 Give at least two different proofs that a set X with n elements has exactly 2 n subsets. 1.35 A weekly lottery asks you to select 5 different numbers between 1 and 45. At the week’s end, 5 such numbers are drawn at random, and you win the jackpot if all your numbers match the drawn numbers. What is your chance of winning? 1.33 (i) (ii) 34 N UMBER T HEORY CH. 1 Definition. Define the n th derivative f(n) (x) of a function f (x) inductively: set f (0) (x) = f (x) and, if n ≥ 0, define f(n+1) (x) = ( f (n) )0 (x). 1.36 Assume that “termbyterm” differentiation holds for power series: if f (x) = c 0 + c1 x + c2 x 2 + · · · + cn x n + · · · , then the power series for the derivative f 0 (x) is f 0 (x) = c1 + 2c2 x + 3c3 x 2 + · · · + ncn x n−1 + · · · . (i) (ii) Prove that f (0) = c0 . Prove, for all n ≥ 0, that f (n) (x) = n!cn + (n + 1)!cn+1 x + x 2 gn (x), where gn (x) is some power series . (iii) Prove that cn = f (n) (x)(0)/n! for all n ≥ 0. (Of course, this is Taylor’s formula.) *1.37 (Leibniz) A function f : → is called a C ∞ function if it has an nth derivative f (n) (x) for every n ≥ 0. Prove that if f and g are C ∞ functions, then n X n (k) ( f g)(n) (x) = f (x) · g (n−k) (x). k k=0 1.38 (i) If z = a + i b 6= 0, prove that 1 a b = 2 −i 2 . z a + b2 a + b2 −1 (ii) √ If z lies on the unit circle, prove that z = z. 1.39 Find i . *1.40 (i) If z = r [cos θ + i sin θ ], show that √ w = n r [cos(θ/n) + i sin(θ/n)] (ii) 1.41 1.3 (i) (ii) is an nth root of z, where r ≥ 0. Show that every nth root of z has the form ζ k w, where ζ is a primitive nth root of unity and k = 0, 1, 2, . . . , n − 1. √ Find 8 + 15i . Find all the fourth roots of 8 + 15i . G REATEST C OMMON D IVISORS This is an appropriate time to introduce notation for some popular sets of numbers other than (denoting the integers) and (denoting the natural numbers). = the set of all rational numbers (or fractions), that is, all numbers of the form a/b, where a and b are integers and b 6 = 0 (after the word quotient) G REATEST C OMMON D IVISORS 35 = the set of all real numbers = the set of all complex numbers Long division involves dividing an integer b by a nonzero integer a, giving r b =q+ , a a where q is an integer and 0 ≤ r/a < 1. We clear denominators to get a statement wholly in . Theorem 1.29 (Division Algorithm). there exist unique integers q and r with b = qa + r and Given integers a and b with a 6 = 0, 0 ≤ r < a. Proof. We will prove the theorem in the special case in which a > 0 and b ≥ 0; Exercise 1.42 on page 51 asks the reader to complete the proof. Long division involves finding the largest integer q with qa ≤ b, which is the same thing as finding the smallest nonnegative integer of the form b − qa. We formalize this. The set C of all nonnegative integers of the form b − na, where n ≥ 0, is not empty because it contains b = b − 0a (we are assuming that b ≥ 0). By the Least Integer Axiom, C contains a smallest element, say, r = b − qa (for some q ≥ 0); of course, r ≥ 0, by its definition. If r ≥ a, then b − (q + 1)a = b − qa − a = r − a ≥ 0. Hence, r −a = b−(q+1)a is an element of C that is smaller than r , contradicting r being the smallest integer in C. Therefore, 0 ≤ r < a. It remains to prove the uniqueness of q and r . Suppose that b = qa + r = q 0 a + r 0 , where 0 ≤ r, r 0 < a, so that (q − q 0 )a = r 0 − r. We may assume that r 0 ≥ r , so that r 0 − r ≥ 0 and hence q − q 0 ≥ 0. If q 6 = q 0 , then q − q 0 ≥ 1 (for q − q 0 is an integer); thus, since a > 0, (q − q 0 )a ≥ a. On the other hand, since r 0 < a, Proposition A.2 gives r 0 − r < a − r ≤ a. Therefore, (q − q 0 )a ≥ a and r 0 − r < a, contradicting the given equation (q − q 0 )a = r 0 − r . We conclude that q = q 0 and hence r = r 0 . • 36 N UMBER T HEORY CH. 1 Definition. If a and b are integers with a 6 = 0, then the integers q and r occurring in the division algorithm are called the quotient and the remainderafter dividing b by a. For example, there are only two possible remainders after dividing by 2, namely, 0 and 1. A number m is even if the remainder is 0; m is odd if the remainder is 1. Thus, either m = 2q or m = 2q + 1. Warning! The division algorithm makes sense, in particular, when b is negative. A careless person may assume that b and −b leave the same remainder after dividing by a, and this is usually false. For example, let us divide 60 and −60 by 7. 60 = 7 · 8 + 4 and − 60 = 7 · (−9) + 3. Thus, the remainders after dividing 60 and −60 by 7 are different (see Exercise 1.77 on page 71). The next result shows that there is no largest prime. Corollary 1.30. There are infinitely many primes. Proof. (Euclid) Suppose, on the contrary, that there are only finitely many primes. If p1 , p2 , . . . , pk is the complete list of all the primes, define M = ( p1 · · · pk ) + 1. By Theorem 1.2, M is either a prime or a product of primes. But M is neither a prime (M > pi for every i ) nor does it have any prime divisor pi , for dividing M by pi gives remainder 1 and not 0. For example, dividing M by p1 gives M = p1 ( p2 · · · pk ) + 1, so that the quotient and remainder are q = p2 · · · pk and r = 1; dividing M by p2 gives M = p2 ( p1 p3 · · · pk ) + 1, so that q = p1 p3 · · · pk and r = 1; and so forth. The assumption that there are only finitely many primes leads to a contradiction, and so there must be an infinite number of them. • An algorithm solving a problem is a set of directions which gives the correct answer after a finite number of steps, never at any stage leaving the user in doubt as to what to do next. The division algorithm is an algorithm in this sense: one starts with a and b and ends with q and r . The appendix at the end of the book treats algorithms more formally, using pseudocodes, which are general directions that can easily be translated into a programming language. For example, here is a pseudocode for the division algorithm. 1: 2: 3: 4: 5: 6: 7: Input: b ≥ a > 0 Output: q, r q := 0; r := b WHILE r ≥ a DO r := r − a q := q + 1 END WHILE G REATEST C OMMON D IVISORS 37 Definition. If a and b are integers, then a is a divisor of b if there is an integer d with b = ad (synonyms are a divides b and also b is a multiple of a). We denote this by a  b. Note that 3  6, because 6 = 3 × 2, but that 3 5 (that is, 3 does not divide 5): even though 5 = 3 × 35 , the fraction 53 is not an integer. The numbers ±1 and ±b are divisors of any integer b. We always have b  0 (because 0 = b × 0); on the other hand, if 0  b, then b = 0 (because there is some d with b = 0 × d = 0). If a and b are integers with a 6 = 0, then a is a divisor of b if and only if the remainder r given by the division algorithm is 0. If a is a divisor of b, then the remainder r given by the division algorithm is 0; conversely, if the remainder r is 0, then a is a divisor of b. Definition. A common divisor of integers a and b is an integer c with c  a and c  b. The greatest common divisor of a and b, denoted by gcd(a, b) [or, more briefly, by (a, b)], is defined by ( 0 if a = 0 = b gcd(a, b) = the largest common divisor of a and b otherwise. The notation (a, b) for the gcd is, obviously, the same notation used for the ordered pair. The reader should have no difficulty understanding the intended meaning from the context in which the symbol occurs. If a and m are positive integers with a  m, say, m = ab, we claim that a ≤ m. Since 0 < b, we have 1 ≤ b, because b is an integer, and so a ≤ ab = m. It follows that gcd’s always exist. If c is a common divisor of a and b, then so is −c. Since one of ±c is nonnegative, the gcd is always nonnegative. It is easy to check that if at least one of a and b is nonzero, then (a, b) > 0. Proposition 1.31. If p is a prime and b is any integer, then ( p if p  b ( p, b) = 1 otherwise. Proof. A common divisor c of p and a is, of course, a divisor of p. But the only positive divisors of p are p and 1, and so ( p, a) = p or 1; it is p if p  a, and it is 1 otherwise. • 38 N UMBER T HEORY Definition. CH. 1 A linear combination of integers a and b is an integer of the form sa + tb, where s and t are integers. The next result is one of the most useful properties of gcd’s. Theorem 1.32. If a and b are integers, then gcd(a, b) is a linear combination of a and b. Proof. We may assume that at least one of a and b is not zero (otherwise, the gcd is 0 and the result is obvious). Consider the set I of all the linear combinations: I = {sa + tb : s, t in }. Both a and b are in I (take s = 1 and t = 0 or vice versa). It follows that I contains positive integers (if a 6 = 0, then I contains ±a), and hence the set P of all those positive integers that lie in I is nonempty. By the Least Integer Axiom, P contains a smallest positive integer, say, d, which we claim is the gcd. Since d is in I , it is a linear combination of a and b: there are integers s and t with d = sa + tb. Let us show that d is a common divisor by trying to divide each of a and b by d. The division algorithm gives a = qd + r , where 0 ≤ r < d. If r > 0, then r = a − qd = a − q(sa + tb) = (1 − qs)a + (−qt)b is in P, contradicting d being the smallest element of P. Hence r = 0 and d  a; a similar argument shows that d  b. Finally, if c is a common divisor of a and b, then a = ca 0 and b = cb0 , so that c divides d, for d = sa + tb = c(sa 0 + tb0 ). But if c  d, then c ≤ d, and so d is the gcd of a and b. • If d = gcd(a, b) and if c is a common divisor of a and b, then c ≤ d. The next theorem shows that more is true: c  d for every common divisor c. Corollary 1.33. Let a and b be integers. A nonnegative common divisor d is their gcd if and only if c  d for every common divisor c. Proof. Necessity (i.e., the implication ⇒) That every common divisor c of a and b is a divisor of d = sa + tb, has already been proved at the end of the proof of Theorem 1.32. Sufficiency (i.e., the implication ⇐) Let d denote the gcd of a and b, and let d 0 be a nonnegative common divisor divisible by every common divisor c. Thus, G REATEST C OMMON D IVISORS 39 d 0 ≤ d, because c ≤ d is for every common divisor c. On the other hand, d itself is a common divisor, and so d  d 0 , by hypothesis. Hence, d ≤ d 0 , and so d = d 0 . • The proof of Theorem 1.32 contains an idea that will be used again. Corollary 1.34. Let I be a subset of such that (i) 0 is in I ; (ii) if a and b are in I , then a − b is in I ; (iii) if a is in I and q is in , then qa is in I . Then there is a nonnegative integer d in I with I consisting precisely of all the multiples of d. Proof. If I consists of only the single integer 0, take d = 0. If I contains a nonzero integer a, then (−1)a = −a is in I , by (iii). Thus, I contains ±a, one of which is positive. By the Least Integer Axiom, I contains a smallest positive integer; call it d. We claim that every element a in I is a multiple of d. The division algorithm gives integers q and r with a = qd + r , where 0 ≤ r < d. Since d is in I , so is qd, by (iii), and so (ii) gives r = a − qd in I . But r < d, the smallest positive element of I , and so r = 0; thus, a is a multiple of d. • The next result is of great interest, for it gives one of the most important characterizations of prime numbers. Euclid’s lemma is used frequently (at least ten times in this chapter alone), and an analog of it for irreducible polynomials is equally important. Looking further ahead, this lemma motivates the notion of prime ideal. Theorem 1.35 (Euclid’s Lemma). If p is a prime and p  ab, then p  a or p  b. More generally, if a prime p divides a product a1 a2 · · · an , then it must divide at least one of the factors ai . Conversely, if m ≥ 2 is an integer such that m  ab always implies m  a or m  b, then m is a prime. Proof. Assume that p a; that is, p does not divide a; we must show that p  b. Now the gcd ( p, a) = 1, by Proposition 1.31. By Theorem 1.32, there are integers s and t with 1 = sp + ta, and so b = spb + tab. Since p  ab, we have ab = pc for some integer c, so that b = spb + t pc = p(sb + tc) and p  b. The second statement now follows easily by induction on n ≥ 2. 40 N UMBER T HEORY CH. 1 We prove the contrapositive: if m is composite, then there is a product ab divisible by m, yet neither factor is divisible by m. Since m is composite, m = ab, where a < m and b < m. Thus, m divides ab, but m divides neither factor (if m  a, then m ≤ a). • Here is a concrete illustration showing that Euclid’s lemma is not true in general: 6  12 = 4 × 3, but 6 4 and 6 3. Proposition 1.36. If p is a prime, then p  p for 0 < j < p. j Proof. Recall that p p( p − 1) · · · ( p − j + 1) p! = . = j !( p − j )! j! j Cross multiplying gives p = p( p − 1) · · · ( p − j + 1), j! j p so that p  j ! j . If p  j !, then Euclid’s lemma says that p would have to divide some factor 1, 2, . . . , j of j !. Since 0 < j < p, each factor of j ! is strictly less than p, and so p is not a divisor of any of them. Therefore, p j !. As p  j ! pj , Euclid’s lemma now shows that p must divide pj . • 4 Notice that the assumption that p is prime is needed; for example, 2 = 6, but 4 6. Definition. Call integers a and b relatively prime if their gcd is 1. Thus, a and b are relatively prime if their only common divisors are ±1; moreover, 1 is a linear combination of a and b. For example, 2 and 3 are relatively prime, as are 8 and 15. Here is a generalization of Euclid’s lemma having the same proof. Corollary 1.37. Let a, b, and c be integers. If c and a are relatively prime and if c  ab, then c  b. Proof. By hypothesis, ab = cd for some integer d. There are integers s and t with 1 = sc + ta, and so b = scb + tab = scb + tcd = c(sb + td). • We see that it is important to know proofs: Corollary 1.37 does not follow from the statement of Euclid’s lemma, but it does follow from its proof. G REATEST C OMMON D IVISORS 41 Definition. An expression a/b for a rational number (where a and b are integers) is in lowest terms if a and b are relatively prime. Lemma 1.38. terms. Every nonzero rational number r has an expression in lowest Proof. Since r is rational, r = a/b for integers a and b. If d = (a, b), then a = a 0 d, b = b0 d, and a/b = a 0 d/b0d = a 0 /b0 . But (a 0 , b0 ) = 1, for if d 0 > 1 is a common divisor of a 0 and b0 , then d 0 d > d is a larger common divisor of a and b. • Here is a description of the Euler φfunction that does not mention cyclotomic polynomials. Proposition 1.39. If n ≥ 1 is an integer, then φ(n) is the number of integers k with 1 ≤ k ≤ n and (k, n) = 1. Proof. It suffices to prove that e 2π ik/n is a primitive nth root of unity if and only if k and n are relatively prime. If k and n are not relatively prime, then n = dr and k = ds, where d, r , ds = rs , so and s are integers, and d > 1; it follows that r < n. Hence, nk = dr 2π ik/n r 2π is/r r 2π ik/n that (e ) = (e ) = 1, and hence e is not a primitive nth root of unity. Conversely, suppose that ζ = e 2π ik/n is not a primitive nth root of unity. Lemma 1.26 says that ζ must be a dth root of unity for some divisor d of n with d < n; that is, there is 1 ≤ m ≤ d with ζ = e2π ik/n = e2π im/d = e2π imr/dr = e2π imr/n . Since both k and mr are in the range between 1 and n, it follows that k = mr (if 0 ≤ x, y < 1 and e2π i x = e2π iy , then x = y); that is, r is a divisor of k and of n, and so k and n are not relatively prime. • Proposition 1.40. √ 2 is irrational. √ √ Proof. Suppose, on the contrary, that 2 is rational; that is, 2 = a/b. We may assume that a/b is in lowest terms; that is, (a, b) = 1. Squaring, a 2 = 2b2 . By Euclid’s lemma17 , 2  a, so that 2m = a, hence 4m 2 = a 2 = 2b2 , and 2m 2 = b2 . Euclid’s lemma now gives 2  b, contradicting (a, b) = 1. • 17 This proof can be made more elementary; one needs only Proposition 1.11. 42 N UMBER T HEORY CH. 1 This last result is significant in the history of mathematics. The ancient Greeks defined number to mean positive integer, while (positive) rational numbers were √ viewed as “ratios” a : b (which we can interpret as fractions a/b). That 2 is irrational was a shock to the Pythagoreans (around 600 BC), for it √ told them that 2 could not be defined in terms of numbers (positive integers) alone. On the other hand, √ they knew that the diagonal of a square having sides of length 1 has length 2. Thus, there is no numerical solution to the equation x 2 = 2, but there is a geometric solution. By the time of Euclid, (around 325 BC), this problem was resolved by splitting mathematics into two different disciplines: algebra and geometry. This resolution is probably one of the main reasons that the golden age of classical mathematics declined in Europe after the rise of the Roman Empire. For example, there were geometric ways of viewing addition, subtraction, multiplication, and division of segments (see Theorem 4.46), but it was virtually impossible to do any algebra. A sophisticated geometric argument (due to Eudoxus and given in Euclid’s Elements) was needed to prove the version of crossmultiplication saying that if a : b = c : d, then a : c = b : d. We quote van der Waerden, Science Awakening, page 125: Nowadays√we say that the length of the diagonal is the “irrational number” 2, and we feel superior to the poor Greeks who “did not know irrationals.” But the Greeks √ knew irrational ratios very well . . . That they did not consider 2 as a number was not a result of ignorance, but of strict adherence to the definition of number. Arithmos means quantity, therefore whole number. Their logical rigor did not even allow them to admit fractions; they replaced them by ratios of integers. For the Babylonians, every segment and every area simply represented a number . . . When they could not determine a square root exactly, they calmly accepted an approximation. Engineers and natural scientists have always done this. But the Greeks were concerned with exact knowledge, with “the diagonal itself,” as Plato expresses it, not with an acceptable approximation. In the domain of numbers (positive integers), the equation x 2 = 2 cannot be solved, not even in that of ratios of numbers. But it is solvable in the domain of segments; indeed the diagonal of the unit square is a solution. Consequently, in order to obtain exact solutions of quadratic equations, we have to pass from the domain of numbers (positive integers) to that of geometric magnitudes. Geometric algebra is valid also for irrational segments and is nevertheless an exact science. It is therefore logical necessity, not the mere delight in the visible, which compelled the Pythagoreans to transmute their G REATEST C OMMON D IVISORS 43 algebra into a geometric form. Even though the Greek definition of number is no longer popular, their dichotomy still persists. For example, almost all American high schools teach one year of algebra followed by one year of geometry, instead of two years in which both subjects are developed together. The problem of defining number has arisen several times since the classical Greek era. In the 1500s, mathematicians had to deal with negative numbers and with complex numbers (see our discussion of cubic polynomials in Chapter 5); the description of real numbers generally accepted today dates from the late 1800s. There are echos of ancient Athens in our time. L. Kronecker (1823–1891) wrote, Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk. Go