Benjamin Fine Gerhard Rosenberger Number Theory An Introduction via the Distribution of Primes Birkha¨user Boston • Basel • Berlin BenjaminFine GerhardRosenberger FairfieldUniversity Universita¨tDortmund DepartmentofMathematics FachbereichMathematik Fairfield,CT06824 D-44221Dortmund U.S.A. Germany CoverdesignbyAlexGerasev. MathematicsSubjectClassification(2000):11A01,11A03,11M01,11R01,11Z05,11T71,11H01, 20A01,20G01,20K01,14G01,08A01 LibraryofCongressControlNumber:2006931568 ISBN-100-8176-4472-5 e-ISBN-100-8176-4545-1 ISBN-13978-0-8176-4472-7 e-ISBN-13978-0-8176-4541-0 Printedonacid-freepaper. (cid:2)c2007Birkha¨userBoston Allrightsreserved.Thisworkmaynotbetranslatedorcopiedinwholeorinpartwithoutthewritten permission of the publisher (Birkha¨user Boston, c/o Springer Science+Business Media LLC, 233 SpringStreet,NewYork,NY10013,USA)andtheauthor,exceptforbriefexcerptsinconnectionwith reviewsorscholarlyanalysis.Useinconnectionwithanyformofinformationstorageandretrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafterdevelopedisforbidden. Theuseinthispublicationoftradenames,trademarks,servicemarksandsimilarterms,evenifthey arenotidentifiedassuch,isnottobetakenasanexpressionofopinionastowhetherornottheyare subjecttoproprietaryrights. 9 8 7 6 5 4 3 2 1 www.birkhauser.com (TXQ/EB) To our families: Linda, Carolyn, David, Scott, Shane, and Sawyer, Katariina, Anja, and Aila Contents Preface ......................................................... xi 1 IntroductionandHistoricalRemarks............................ 1 2 BasicNumberTheory......................................... 7 2.1 TheRingofIntegers ........................................ 7 2.2 Divisibility,Primes,andComposites .......................... 11 2.3 TheFundamentalTheoremofArithmetic....................... 16 2.4 CongruencesandModularArithmetic ......................... 21 2.4.1 BasicTheoryofCongruences.......................... 22 2.4.2 TheRingofIntegersModulon......................... 23 2.4.3 UnitsandtheEulerPhiFunction ....................... 26 2.4.4 Fermat’sLittleTheoremandtheOrderofanElement...... 31 2.4.5 OnCyclicGroups.................................... 34 2.5 TheSolutionofPolynomialCongruencesModulom ............. 37 2.5.1 LinearCongruencesandtheChineseRemainderTheorem .. 37 2.5.2 Higher-DegreeCongruences........................... 42 2.6 QuadraticReciprocity....................................... 45 3 TheInfinitudeofPrimes ...................................... 55 3.1 TheInfinitudeofPrimes..................................... 55 3.1.1 SomeDirectProofsandVariations...................... 55 3.1.2 SomeAnalyticProofsandVariations.................... 58 3.1.3 TheFermatandMersenneNumbers .................... 61 3.1.4 TheFibonacciNumbersandtheGoldenSection .......... 65 3.1.5 SomeSimpleCasesofDirichlet’sTheorem .............. 78 3.1.6 ATopologicalProofandaProofUsingCodes ............ 83 3.2 SumsofSquares ........................................... 86 3.2.1 PythagoreanTriples .................................. 87 3.2.2 Fermat’sTwo-SquareTheorem......................... 89 3.2.3 TheModularGroup .................................. 94 viii Contents 3.2.4 Lagrange’sFour-SquareTheorem ...................... 100 3.2.5 TheInfinitudeofPrimesThroughContinuedFractions..... 102 3.3 Dirichlet’sTheorem ........................................ 104 3.4 TwinPrimeConjectureandRelatedIdeas ...................... 121 3.5 PrimesBetweenx and2x.................................... 122 3.6 ArithmeticFunctionsandtheMöbiusInversionFormula.......... 123 4 TheDensityofPrimes ........................................ 133 4.1 ThePrimeNumberTheorem: EstimatesandHistory ............. 133 4.2 Chebychev’sEstimateandSomeConsequences ................. 136 4.3 EquivalentFormulationsofthePrimeNumberTheorem.......... 149 4.4 TheRiemannZetaFunctionandtheRiemannHypothesis......... 157 4.4.1 TheRealZetaFunctionofEuler........................ 158 4.4.2 AnalyticFunctionsandAnalyticContinuation ............ 163 4.4.3 TheRiemannZetaFunction ........................... 166 4.5 ThePrimeNumberTheorem ................................. 173 4.6 TheElementaryProof....................................... 180 4.7 SomeExtensionsandComments.............................. 185 5 PrimalityTesting: AnOverview ................................ 197 5.1 PrimalityTestingandFactorization............................ 197 5.2 SievingMethods ........................................... 198 5.2.1 Brun’sSieveandBrun’sTheorem ...................... 204 5.3 PrimalityTestingandPrimeRecords .......................... 212 5.3.1 PseudoprimesandProbabilisticTesting.................. 218 5.3.2 TheLucas–LehmerTestandPrimeRecords .............. 225 5.3.3 SomeAdditionalPrimalityTests........................ 231 5.4 CryptographyandPrimes.................................... 234 5.4.1 SomeNumber-TheoreticCryptosystems................. 237 5.4.2 PublicKeyCryptographyandtheRSAAlgorithm......... 240 5.5 TheAKSAlgorithm ........................................ 243 6 PrimesandAlgebraicNumberTheory........................... 253 6.1 AlgebraicNumberTheory ................................... 253 6.2 UniqueFactorizationDomains ............................... 255 6.2.1 EuclideanDomainsandtheGaussianIntegers ............ 261 6.2.2 PrincipalIdealDomains .............................. 268 6.2.3 PrimeandMaximalIdeals............................. 272 6.3 AlgebraicNumberFields .................................... 275 6.3.1 AlgebraicExtensionsofQQQ............................. 282 6.3.2 AlgebraicandTranscendentalNumbers.................. 284 6.3.3 SymmetricPolynomials............................... 287 6.3.4 DiscriminantandNorm ............................... 290 6.4 AlgebraicIntegers .......................................... 294 6.4.1 TheRingofAlgebraicIntegers......................... 296 Contents ix 6.4.2 IntegralBases ....................................... 297 6.4.3 QuadraticFieldsandQuadraticIntegers ................. 300 6.4.4 TheTranscendenceofeandπ ......................... 303 6.4.5 TheGeometryofNumbers: MinkowskiTheory........... 306 6.4.6 Dirichlet’sUnitTheorem.............................. 308 6.5 TheTheoryofIdeals........................................ 311 6.5.1 UniqueFactorizationofIdeals ......................... 313 6.5.2 AnApplicationofUniqueFactorization ................. 319 6.5.3 TheIdealClassGroup ................................ 321 6.5.4 NormsofIdeals ..................................... 323 6.5.5 ClassNumber ....................................... 326 BibliographyandCitedReferences ................................. 333 Index........................................................... 337 Preface Numbertheoryisfascinating. Resultsaboutnumbersoftenappearmagical,bothin theirstatementsandintheeleganceoftheirproofs. Nowhereisthismoreevidentthan inresultsaboutthesetofprimenumbers. Theprimenumbertheorem,whichgivesthe asymptoticdensityoftheprimenumbers,isoftencitedasthemostsurprisingresult inallofmathematics. Itcertainlyistheresultthatishardesttojustifyintuitively. The prime numbers form the cornerstone of the theory of numbers. Many, if not most, results in number theory proceed by considering the case of primes and then pasting the result together for all integers using the fundamental theorem of arithmetic. The purpose of this book is to give an introduction and overview of numbertheorybasedonthecentralthemeofthesequenceofprimes. Therichnessof thissomewhatuniqueapproachbecomesclearonceonerealizeshowmuchnumber theoryandmathematicsingeneralareneededinordertolearnandtrulyunderstandthe primenumbers. Ourapproachprovidesasolidbackgroundinthestandardmaterial as well as presenting an overview of the whole discipline. All the essential topics are covered: fundamental theorem of arithmetic, theory of congruences, quadratic reciprocity, arithmetic functions, the distribution of primes. In addition, there are firmintroductionstoanalyticnumbertheory,primalitytestingandcryptography,and algebraicnumbertheoryaswellasmanyinterestingsidetopics. Fulltreatmentsand proofsaregiventobothDirichlet’stheoremandtheprimenumbertheorem. Thereis acompleteexplanationofthenewAKSalgorithm,whichshowsthatprimalitytesting isofpolynomialtime. Inalgebraicnumbertheorythereisacompletepresentation ofprimesandprimefactorizationsinalgebraicnumberfields. Thebookgrewoutofnotesfromseveralcoursesgivenforadvancedundergrad- uates in the United States and for teachers in Germany. The material on the prime numbertheoremgrewoutofseminarsalsogivenbothattheUniversityofDortmund andatFairfieldUniversity. Theintendedaudienceisupper-levelundergraduatesand beginning graduate students. The notes on which the book was based were used effectivelyinsuchcoursesinboththeUnitedStatesandGermany. Theprerequisites areaknowledgeofcalculusandmultivariablecalculusandsomelinearalgebra. The necessary ideas from abstract algebra and complex analysis are introduced in the book. There are many interesting exercises ranging from simple to quite difficult. xii Preface Solutionsandhintsareprovidedtoselectedexercises. Wehavewrittenthebookin whatwefeelisauser-friendlystylewithmanydiscussionsofthehistoryofvarious topics. Itisouropinionthatthisbookisalsoidealforself-study. Therearetwobasicfactsconcerningthesequenceofprimesonwhichthisbook is focused and from which much of the theory of numbers is introduced. The first fact is that there are infinitely many primes. This fact was of course known since at least the time of Euclid. However, there are a great many proofs of this result notrelatedtoEuclid’soriginalproof. Byconsideringandpresentingmanyofthese proofs,awideareaofmodernnumbertheoryiscovered. Thisincludesthefactthat theprimesarenumerousenoughsothatthereareinfinitelymanyinanyarithmetic progression an+b with a,b relatively prime (Dirichlet’s theorem). The proof of Dirichlet’stheoremallowsustointroduceanalyticmethods. In contrast to there being infinitely many primes, the density of primes thins out. Wefirstencounterthisfactinthestartling(buteasilyproved)resultthatthere are arbitrarily large gaps in the sequence of primes. The exact nature of how the sequence of primes thins out is formalized in the prime number theorem, which as alreadymentioned,manypeopleconsiderthemostsurprisingresultinmathematics. Presentingtheproofandtheideassurroundingtheproofoftheprimenumbertheorem allowsustointroduceanddiscussalargeportionofanalyticnumbertheory. Algebraicnumbertheoryaroseoriginallyasanattempttoextenduniquefactoriza- tiontoalgebraicnumberrings. Weusetheapproachoflookingatprimesandprime factorizations to present a fairly comprehensive introduction to algebraic number theory. Finally, modern crypotography is intimately tied to number theory. Especially crucial in this connection is primality testing. We discuss various primality testing methods,includingtherecentlydevelopedAKSalgorithm,andthenprovideabasic introductiontocryptography. Thereareseveralwaysthatthisbookcanbeusedforcourses. Chapters1and2 togetherwithselectionsfromtheremainingchapterscanbeusedforaone-semester courseinnumbertheoryforundergraduatesorbeginninggraduatestudents. Theonly prerequisitesareabasicknowledgeofmathematicalproofs(induction,etc.)andsome knowledgeofcalculus. Alltherestisself-contained, althoughwedousealgebraic methods, so that some knowledge of basic abstract algebra would be beneficial. A year-longcoursefocusingonanalyticmethodscanbedonefromChapters1,2,3,and4 andselectionsfrom5and6,whileayear-longcoursefocusingonalgebraicnumber theory can be fashioned from Chapters 1, 2, 3, and 6 and selections from 4 and 5. Therearealsopossibilitiesforusingthebookforone-semesterintroductorycourses inanalyticnumbertheory,centeringonChapter4,orforaone-semesterintroductory courseinalgebraicnumbertheory,centeringonChapter6. Somesuggestedcourses: BasicIntroductoryOne-SemesterNumberTheoryCourse: ChapterOne,ChapterTwo,Sections3.1,4.1,4.2,5.1,5.3,5.4,6.1 Year-LongCourseFocusingonAnalyticNumberTheory: Chapter1,Chapter2,Chapter3,Chapter4,Sections5.1,5.3,5.4,6.1 Preface xiii Year-LongCourseFocusingonAlgebraicNumberTheory: Chapter1,Chapter2,Chapter3,Chapter6,Sections4.1,4.2,5.1,5.3,5.4 One-SemesterCourseFocusingonAnalyticNumberTheory: Chapter1,Chapter2(asneeded),Sections3.1,3.1.5,3.3,3.4,3.5,Chapter4 One-SemesterCourseFocusingonAlgebraicNumberTheory: Chapter1,Chapter2(asneeded),Chapter6 We would like to thank the many people who have read through other prelimi- naryversionsofthesenotesandmadesuggestions. IncludedamongthemareKati Bencsath andAl Thaler as well as the many students who have taken the courses. Inparticular,wewouldliketothankPeterAckermann,whoreadthroughthewhole manuscript, both proofreading it and making mathematical suggestions. Peter was alsoheavilyinvolvedintheseminarsontheprimenumbertheoremfromwhichmuch of the material in Chapter 4 comes. We also thank the editors at Birkhäuser, who didadetailedreadingofthemanuscriptandmademanyimportantsuggestionsand improvements. BenjaminFine—Fairfield,CT,USA GerhardRosenberger—Dortmund,Germany January,2006