EncyclopaediaofMathematicalSciences Volume49 NumberTheoryI Yuri Ivanovic Manin Alexei A. Panchishkin Introduction to Modern Number Theory Fundamental Problems, Ideas and Theories Second Edition 123 Authors YuriIvanovicManin Max-Planck-InstitutfürMathematik Vivatsgasse7 53111Bonn,Germany e-mail:[email protected] AlexeiA.Panchishkin Universit´eJosephFourierUMR5582 InstitutFourier 38402SaintMartind’H`eres,France e-mail:[email protected] FoundingeditoroftheEncyclopaediaofMathematicalSciences: R.V.Gamkrelidze OriginalRussianversionofthefirstedition waspublishedbyVINITI,Moscowin1990 ThefirsteditionofthisbookwaspublishedasNumberTheoryI, Yu.I.Manin,A.A.Panchishkin(Authors),A.N.Parshin,I.R.Shafarevich(Eds.), Vol.49oftheEncyclopaediaofMathematicalSciences MathematicsSubjectClassification(2000): 11-XX(11A,11B,11D,11E,11F,11G,11R,11S,11U,11Y),14-XX,20-XX,37-XX,03-XX ISSN0938-0396 ISBN-10 3-540-20364-8SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-20364-3SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialisconcerned, specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation,broadcasting,reproductionon microfilmorinanyotherway,andstorageindatabanks.Duplicationofthispublicationorpartsthereofis permittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965,initscurrentversion,and permissionforusemustalwaysbeobtainedfromSpringer.ViolationsareliableforprosecutionundertheGerman CopyrightLaw. SpringerisapartofSpringerScience+BusinessMediaGmbH springeronline.com ©Springer-VerlagBerlinHeidelberg2005 PrintedinTheNetherlands Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply,evenin theabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantpro- tectivelawsandregulationsandthereforefreeforgeneraluse. Typesetting:bytheauthorsusingaSpringerLATEXmacropackage CoverDesign:E.Kirchner,Heidelberg,Germany Printedonacid-freepaper 46/3142sz 543210 Preface The present book is a new revised and updated version of “Number Theory I. Introduction to Number Theory” by Yu.I.Manin and A.A.Panchishkin, ap- peared in 1989 in Moscow (VINITI Publishers) [Ma-PaM], and in English translation [Ma-Pa] of 1995 (Springer Verlag). The original book had been conceived as a part of a vast project, “En- cyclopaedia of Mathematical Sciences”. Accordingly, our task was to provide a series of introductory essays to various chapters of number theory, lead- ing the reader from illuminating examples of number theoretic objects and problems,throughgeneralnotionsandtheories,developedgraduallybymany researchers,tosomeofthehighlightsofmodernmathematicsandgreat,some- times nebulous designs for future generations. Inpreparingthisnewedition,wetriedtokeepthisinitialvisionintact.We present many precise definitions, but practically no complete proofs. We try to show the logic of number-theoretic thought and the wide context in which variousconstructionsaremade,butfordetailedstudyoftherelevantmaterials thereaderwillhavetoturntooriginalpapersortoothermonographs.Because of lack of competence and/or space, we had to - reluctantly - omit many fascinating developments. The new sections written for this edition, include a sketch of Wiles’ proof of Fermat’s Last Theorem, and relevant techniques coming from a synthesis of various theories of Part II; the whole Part III dedicated to arithmetical cohomology and noncommutative geometry; a report on point counts on va- rieties with many rational points; the recent polynomial time algorithm for primality testing, and some others subjects. For more detailed description of the content and suggestions for further reading, see Introduction. VI Preface We are very pleased to express our deep gratitude to Prof. M.Marcolli for her essential help in preparing the last part of the new edition. We are very grateful to Prof. H.Cohen for his assistance in updating the book, es- pecially Chapter 2. Many thanks to Prof. Yu.Tschinkel for very useful sug- gestions, remarks, and updates; he kindly rewrote §5.2 for this edition. We thank Dr.R.Hill and Dr.A.Gewirtz for editing some new sections of this edi- tion, and St.Kühnlein (Universität des Saarlandes) for sending us a detailed list of remarks to the first edition. Bonn, July 2004 Yu.I.Manin A.A.Panchishkin Contents Part I Problems and Tricks 1 Elementary Number Theory ............................... 9 1.1 Problems About Primes. Divisibility and Primality .......... 9 1.1.1 Arithmetical Notation ............................. 9 1.1.2 Primes and composite numbers ..................... 10 1.1.3 The Factorization Theorem and the Euclidean Algorithm ........................................ 12 1.1.4 Calculations with Residue Classes ................... 13 1.1.5 The Quadratic Reciprocity Law and Its Use .......... 15 1.1.6 The Distribution of Primes ......................... 17 1.2 Diophantine Equations of Degree One and Two.............. 22 1.2.1 The Equation ax+by =c .......................... 22 1.2.2 Linear Diophantine Systems ........................ 22 1.2.3 Equations of Degree Two ........................... 24 1.2.4 The Minkowski–Hasse Principle for Quadratic Forms... 26 1.2.5 Pell’s Equation.................................... 28 1.2.6 Representation of Integers and Quadratic Forms by Quadratic Forms .................................. 29 1.2.7 Analytic Methods ................................. 33 1.2.8 Equivalence of Binary Quadratic Forms .............. 35 1.3 Cubic Diophantine Equations ............................. 38 1.3.1 The Problem of the Existence of a Solution ........... 38 1.3.2 Addition of Points on a Cubic Curve................. 38 1.3.3 The Structure of the Group of Rational Points of a Non–Singular Cubic Curve ......................... 40 1.3.4 Cubic Congruences Modulo a Prime ................. 47 1.4 Approximations and Continued Fractions................... 50 1.4.1 Best Approximations to Irrational Numbers .......... 50 1.4.2 Farey Series ...................................... 50 1.4.3 Continued Fractions ............................... 51 VIII Contents 1.4.4 SL –Equivalence .................................. 53 2 1.4.5 Periodic Continued Fractions and Pell’s Equation...... 53 1.5 Diophantine Approximation and the Irrationality............ 55 1.5.1 Ideas in the Proof that ζ(3) is Irrational.............. 55 1.5.2 The Measure of Irrationality of a Number ............ 56 1.5.3 The Thue–Siegel–Roth Theorem, Transcendental Numbers, and Diophantine Equations................ 57 1.5.4 Proofs of the Identities (1.5.1) and (1.5.2) ............ 58 1.5.5 The Recurrent Sequences a and b ................. 59 n n 1.5.6 Transcendental Numbers and the Seventh Hilbert Problem.......................................... 61 1.5.7 Work of Yu.V. Nesterenko on eπ, [Nes99] ............. 61 2 Some Applications of Elementary Number Theory......... 63 2.1 Factorization and Public Key Cryptosystems................ 63 2.1.1 Factorization is Time-Consuming.................... 63 2.1.2 One–Way Functions and Public Key Encryption....... 63 2.1.3 A Public Key Cryptosystem ........................ 64 2.1.4 Statistics and Mass Production of Primes............. 66 2.1.5 Probabilistic Primality Tests........................ 66 2.1.6 The Discrete Logarithm Problem and The Diffie-Hellman Key Exchange Protocol ............... 67 2.1.7 Computing of the Discrete Logarithm on Elliptic Curves over Finite Fields (ECDLP).................. 68 2.2 Deterministic Primality Tests ............................. 69 2.2.1 Adleman–Pomerance–Rumely Primality Test: Basic Ideas ............................................ 69 2.2.2 Gauss Sums and Their Use in Primality Testing....... 71 2.2.3 Detailed Description of the Primality Test ............ 75 2.2.4 Primes is in P .................................... 78 2.2.5 The algorithm of M. Agrawal, N. Kayal and N. Saxena. 81 2.2.6 Practical and Theoretical Primality Proving. The ECPP (Elliptic Curve Primality Proving by F.Morain, see [AtMo93b]).................................... 81 2.2.7 Primes in Arithmetic Progression.................... 82 2.3 Factorization of Large Integers ............................ 84 2.3.1 Comparative Difficulty of Primality Testing and Factorization ..................................... 84 2.3.2 Factorization and Quadratic Forms .................. 84 2.3.3 The Probabilistic Algorithm CLASNO ............... 85 2.3.4 The Continued Fractions Method (CFRAC) and Real Quadratic Fields .................................. 87 2.3.5 The Use of Elliptic Curves.......................... 90 Contents IX Part II Ideas and Theories 3 Induction and Recursion................................... 95 3.1 Elementary Number Theory From the Point of View of Logic . 95 3.1.1 Elementary Number Theory ........................ 95 3.1.2 Logic ............................................ 96 3.2 Diophantine Sets ....................................... 98 3.2.1 Enumerability and Diophantine Sets ................ 98 3.2.2 Diophantineness of enumerable sets.................. 98 3.2.3 First properties of Diophantine sets ................. 98 3.2.4 Diophantineness and Pell’s Equation................. 99 3.2.5 The Graph of the Exponent is Diophantine ...........100 3.2.6 Diophantineness and Binomial coefficients ............100 3.2.7 Binomial coefficients as remainders ..................101 3.2.8 Diophantineness of the Factorial.....................101 3.2.9 Factorial and Euclidean Division ....................101 3.2.10 Supplementary Results.............................102 3.3 Partially Recursive Functions and Enumerable Sets ..........103 3.3.1 Partial Functions and Computable Functions .........103 3.3.2 The Simple Functions..............................103 3.3.3 Elementary Operations on Partial functions...........103 3.3.4 Partially Recursive Description of a Function .........104 3.3.5 Other Recursive Functions..........................106 3.3.6 Further Properties of Recursive Functions ............108 3.3.7 Link with Level Sets ...............................108 3.3.8 Link with Projections of Level Sets ..................108 3.3.9 Matiyasevich’s Theorem............................109 3.3.10 The existence of certain bijections ...................109 3.3.11 Operations on primitively enumerable sets............111 3.3.12 Gödel’s function...................................111 3.3.13 Discussion of the Properties of Enumerable Sets.......112 3.4 Diophantineness of a Set and algorithmic Undecidability......113 3.4.1 Algorithmic undecidability and unsolvability ..........113 3.4.2 Sketch Proof of the Matiyasevich Theorem ...........113 4 Arithmetic of algebraic numbers...........................115 4.1 Algebraic Numbers: Their Realizations and Geometry........115 4.1.1 Adjoining Roots of Polynomials .....................115 4.1.2 Galois Extensions and Frobenius Elements............117 4.1.3 Tensor Products of Fields and Geometric Realizations of Algebraic Numbers..............................119 4.1.4 Units, the Logarithmic Map, and the Regulator .......121 4.1.5 Lattice Points in a Convex Body ....................123 X Contents 4.1.6 Deduction of Dirichlet’s Theorem From Minkowski’s Lemma ..........................................125 4.2 Decomposition of Prime Ideals, Dedekind Domains, and Valuations..............................................126 4.2.1 Prime Ideals and the Unique Factorization Property ...126 4.2.2 Finiteness of the Class Number .....................128 4.2.3 Decomposition of Prime Ideals in Extensions..........129 4.2.4 Decomposition of primes in cyslotomic fields ..........131 4.2.5 Prime Ideals, Valuations and Absolute Values.........132 4.3 Local and Global Methods................................134 4.3.1 p–adic Numbers...................................134 4.3.2 Applications of p–adic Numbers to Solving Congruences138 4.3.3 The Hilbert Symbol ...............................139 4.3.4 Algebraic Extensions of Q , and the Tate Field........142 p 4.3.5 Normalized Absolute Values ........................143 4.3.6 Places of Number Fields and the Product Formula.....145 4.3.7 Adeles and Ideles..................................146 The Ring of Adeles. ...............................146 The Idele Group ..................................149 4.3.8 The Geometry of Adeles and Ideles ..................149 4.4 Class Field Theory ......................................155 4.4.1 Abelian Extensions of the Field of Rational Numbers ..155 4.4.2 Frobenius Automorphisms of Number Fields and Artin’s Reciprocity Map............................157 4.4.3 The Chebotarev Density Theorem ...................159 4.4.4 The Decomposition Law and the Artin Reciprocity Map .........................159 4.4.5 The Kernel of the Reciprocity Map ..................160 4.4.6 The Artin Symbol .................................161 4.4.7 Global Properties of the Artin Symbol ...............162 4.4.8 A Link Between the Artin Symbol and Local Symbols..163 4.4.9 Properties of the Local Symbol......................164 4.4.10 An Explicit Construction of Abelian Extensions of a Local Field, and a Calculation of the Local Symbol ....165 4.4.11 Abelian Extensions of Number Fields ................168 4.5 Galois Group in Arithetical Problems ......................172 4.5.1 Dividing a circle into n equal parts ..................172 4.5.2 Kummer Extensions and the Power Residue Symbol ...175 4.5.3 Galois Cohomology ................................178 4.5.4 A Cohomological Definition of the Local Symbol ......182 4.5.5 The Brauer Group, the Reciprocity Law and the Minkowski–Hasse Principle .........................184