Undergraduate Texts in Mathematics Editors S. Axler F. W. Gehring K.A. Ribet Springer Science+Business Media, LLC Undergraduate Texts in Mathematics Abbott: Understanding Analysis. Childs: A Concrete Introduction to Anglin: Mathematics: A Concise History Higher Algebra. Second edition. and Philosophy. Chung: Elementary Probability Theory Readings in Mathematics. with Stochastic Processes. Third Anglin/Larnbek: The Heritage of edition. Thales. Cox/Little/O'Shea: Ideals, Varieties, Readings in Mathematics. and Aigorithms. Second edition. Apostol: Introduction to Analytic Croorn: Basic Concepts of Aigebraic Number Theory. Second edition. Topology. Arrnstrong: Basic Topology. Curtis: Linear Algebra: An Introductory Arrnstrong: Groups and Symmetry. Approach. Fourth edition. Axler: Linear Algebra Done Right. DevIin: The Joy of Sets: Fundamentals Second edition. of Contemporary Set Theory. Beardon: Limits: A New Approach to Second edition. Real Analysis. Dixmier: General Topology. BaklNewrnan: Complex Analysis. Driver: Why Math? Second edition. Ebbinghaus/FlumlThomas: Banchoff/Werrner: Linear Algebra Mathematical Logic. Second edition. Through Geometry. Second edition. Edgar: Measure, Topology, and Fractal Berberian: A First Course in Real Geometry. Analysis. EIaydi: An Introduction to Difference Bix: Conics and Cubics: A Equations. Second edition. Concrete Introduction to Algebraic Erdös/Suninyi: Topics in the Theory of Curves. Numbers. Brernaud: An Introduction to Estep: Practical Analysis in One Variable. Probabilistic Modeling. Exner: An Accompaniment to Higher Bressoud: Factorization and Primality Mathernatics. Testing. Exner: Inside Calculus. Bressoud: Second Year Calculus. Fine/Rosenberger: The Fundamental Readings in Mathematics. Theory of Algebra. Brickrnan: Mathematicallntroduction Fischer: Intermediate Real Analysis. to Linear Programming and Game Flanigan/Kazdan: Calculus Two: Linear Theory. and Nonlinear Functions. Second Browder: Mathematical Analysis: edition. An Introduction. Fleming: Functions of Several Variables. Buchmann: Introduction to Second edition. Cryptography. Foulds: Combinatorial Optimization for Buskes/van Rooij: Topological Spaces: Undergraduates. From Distance to Neighborhood. Foulds: Optirnization Techniques: An Callahan: The Geometry of Spacetime: Introduction. An Introduction to Special and General FrankIin: Methods ofMathematical Relavitity. Economics. Carter/van Brunt: The Lebesgue Frazier: An Introduction to Wavelets Stieltjes Integral: A Practical Through Linear Algebra. Introduction. Cederberg: A Course in Modem Geometries. Second edition. (continued after index) Jobn StillweIl Eleßlents of N ußlber Theory With 35 figures Springer John Sti1lwell Mathematics Department University of San Francisco 2130 FultoR Street San Francisco. CA 94117~1080 USA [email protected] EJilflriu[ B(jard s. Axler F.W. Gchring K.A, Ribet Mathematics DL"Partment Malhcmatics Dcpartmcnt Mathematics Departmcnt San Francisco State Eallt Hali University ofCalifomia. Univcrsity University of Michigan Berkeley San Francisco, CA 94132 Ann Arbor, MI 48109 Berkeley, CA 94720·3840 USA USA USA [email protected] fgehrin~mllth.llliI.umich.edu [email protected]:y.edu ISBN 978-1-4419-3066-8 ISBN 978-0-387-21735-2 (eBook) DOI 10.1007/978-0-387-21735-2 Mathcmatics Subjcct ClassifiClllion (2000): il-III or library Congrcss Cataloging-in-!>ublication Data Stil1wcl1, John. E1crnents ofnumber tbeory f John Slillwel1. p. cm. - (1lndeqvaduate tcxlţ in mathematics) Includcs bibliuwaphical references ane! index. QA241 .SRI) 2002 512'.7- Je21 2002030569 Prinled o:: acid-frec paper. @ 2003 Springer Scîence+Business Media New York Originally publîshed by Springer-Verlag New York. lnc in 2003 Softcover reprint of tbe hardcover Ist edition 2003 AII rights reserved. This work lllay not be trans1ated or copied in wbole or in part WItbout tbe written pennission ofthe publisher (Springer Science+8usiness Media, LLC), except for brief excerpts in connec:ion with reviews or scbolarly analysis. Use inconnectioo witb any form of information storage and retrieval. electronic adaptation, computcrsoftware, or by similar or dissimilar methodology now known or bereafter developed is forbidden.rhe use in this publication oftrade f.arnes. trademarks. service t: l arks, and similar tenns, even ifthey are not identified as sueh, is not to be taken as an expression of oplllion as to whetber or not tbey are subject to proprielary rig.hts. 9 8 7 6 5 4 3 2 I v.ww.springer-ny.com ToElaine Preface This book is intended to complement my Elements oi Algebra, and it is similarly motivated by the problem of solving polynomial equations. However, it is independent of the algebra book, and probably easier. In Elements oi Algebra we sought solution by radicals, and this led to the concepts of fields and groups and their fusion in the celebrated theory of Galois. In the present book we seek integer solutions, and this leads to the concepts of rings and ideals which merge in the equally celebrated theory of ideals due to Kummer and Dedekind. Solving equations in integers is the central problem of number theory, so this book is truly a number theory book, with most of the results found in standard number theory courses. However, numbers are best understood through their algebraic structure, and the necessary algebraic concepts rings and ideals-have no better motivation than number theory. The first nontrivial examples of rings appear in the number theory of Euler and Gauss. The concept of ideal-today as routine in ring the ory as the concept of normal subgroup is in group theory-also emerged from number theory, and in quite heroic fashion. Faced with failure of unique prime factorization in the arithmetic of certain generalized "inte gers" , Kummer created in the 1840s a new kind of number to overcome the difficulty. He called them "ideal numbers" because he did not know exactly what they were, though he knew how they behaved. Dedekind in 1871 found that these "ideal numbers" could be realized as sets of actual numbers, and he called these sets ideals. Dedekind found that ideals could be defined quite simply; so much so that a student meeting the concept today might wonder what all the fuss is about. It is only in their role as "ideal numbers", where they realize Kummer's impossible dream, that ideals can be appreciated as a genuinely brilliant idea. vii viii Preface Thus solution in integers-like solution by radicals-is a superb set ting in which to show algebra at its best. It is the right place to introduce rings and ideals and the right place first to apply them. It even gives an opportunity to introduce some exotic rings, such as the quatemions, which we use to prove Lagrange's theorem that every natural number is the sum of four squares. The book is based on two short courses (about 20 lectures each) given at Monash University in recent years; one on elementary number theory and one on ring theory with applications to algebraic number theory. Thus the amount of material is suitable for a one-semester course, with some variation possible through omission of the optional starred sections. A slower-paced course could stop at the end of Chapter 9, at which point most ofthe standard results have been covered, from Euclid's theorem that there are infinitely many primes to quadratic reciprocity. It should be stressed, however, that this is not meant to be a standard number theory course. I have tried to avoid the ad hoc proofs that once gave number theory a bad name, in favor of unifying ideas that work in many situations. These inc1ude algebraic structures but also ideas from elementary number theory, such as the Euc1idean algorithm and unique prime factorization. In particular, I use the Euclidean algorithm as a bridge to Conway's visual theory of quadratic forms, which offers a new approach to the Pell equation. There are exercises at the end of almost every section, so that each new idea or proof receives immediate reinforcement. Some of them focus on specific ideas, while others recapitulate the generalline of argument (in easy steps) to prove a similar result. The purpose of each exercise should be c1ear from the accompanying commentary, so instructors and independent readers alike will be able to find an enjoyable path through the book. My thanks go to the Monash students who took the courses on which the book is based. Their reactions have helped improve the presentation in many ways. I am particularly grateful to Ley Wilson, who showed that it is possible to master the book by independent study. Special thanks go to my wife Elaine, who proofread the first version of the book, and to John Miller and Abe Shenitzer, who carefully read the revised version and saved me from many mathematical and stylistic errors. JOHN STILLWELL South Melbourne, July 2002 Contents Preface vii 1 Natural numbers and integers 1 1.1 Natural numbers . 2 1.2 Induction . . . . . . . . 3 1.3 Integers . . . . . . . . . 5 1.4 Division with remainder 7 1.5 Binary notation . . . . . 8 1.6 Diophantine equations 11 1.7 The Diophantus chord method 14 1.8 Gaussian integers 17 1.9 Discussion...... 20 2 The Euclidean algorithm 22 2.1 The gcd by subtraction . . . . . . . 22 2.2 The gcd by division with remainder 24 2.3 Linear representation of the gcd .. 26 2.4 Primes and factorization ..... . 28 2.5 Consequences of unique prime factorization 30 2.6 Linear Diophantine equations. . . 33 2.7 *The vector Euclidean algorithm 35 2.8 *The map of relatively prime pairs 38 2.9 Discussion. . . . . 40 3 Congruence arithmetic 43 3.1 Congruence mod n .......... . 44 3.2 Congruence c1asses and their arithmetic 45 3.3 Inverses mod p . . . . . ..... 48 ix x Contents 3.4 Fennat's litde theorem ............ . 51 3.5 Congruence theorems of Wilson and Lagrange . 53 3.6 Inverses mod k ...... .. . 55 3.7 Quadratic Diophantine equations 57 3.8 *Primitive roots ...... . 59 3.9 *Existence of primitive roots 62 3.10 Discussion ..... 63 4 The RSA cryptosystem 66 4.1 Trapdoor functions 66 4.2 Ingredients of RSA 69 4.3 Exponentiation mod n . 70 4.4 RSA encryption and decryption . 72 4.5 Digital signatures ..... 73 4.6 Other computational issues 74 4.7 Discussion. . 74 5 The Pell equation 76 5.1 Side and diagonal numbers 77 2l 5.2 The equation:xl - = 1 78 5.3 The group of solutions .. 80 5.4 The general Pell equation and Z[vIn] 81 5.5 The pigeonhole argument ... 84 5.6 *Quadratic fonns . . . . . . . . . 87 5.7 *The map of primitive vectors .. 90 nl 5.8 *Periodicity in the map of:xl - 95 5.9 Discussion. . . . 99 6 The Gaussian integers 101 6.1 Z[i] and its norm ......... . 102 6.2 Divisibility and primes in Z[i] and Z 103 6.3 Conjugates ........ . 105 6.4 Division in Z[i] . . . . . . . 107 6.5 Fennat's two square theorem 109 6.6 Pythagorean tripies . . . . 110 + 6.7 *Primes of the fonn 4n 1 113 6.8 Discussion......... 115