# Number Theory: An Introduction via the Distribution of Primes

Springer Science & Business Media, Jun 4, 2007 - Mathematics - 342 pages
Number theory is fascinating. Results about numbers often appear magical, both in theirstatementsandintheeleganceoftheirproofs. Nowhereisthismoreevidentthan inresultsaboutthesetofprimenumbers. Theprimenumbertheorem,whichgivesthe asymptotic density of the prime numbers, is often cited as the most surprising result in all of mathematics. It certainly is the result that is hardest to justify intuitively. 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 number theory based on the central theme of the sequence of primes. The richness of this somewhat unique approach becomes clear once one realizes how much number theoryandmathematicsingeneralareneededinordertolearnandtrulyunderstandthe prime numbers. Our approach provides a solid background in the standard material 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 ?rm introductions to analytic number theory, primality testing and cryptography, and algebraic number theory as well as many interesting side topics. Full treatments and proofs are given to both Dirichlet’s theorem and the prime number theorem. There is acompleteexplanationofthenewAKSalgorithm,whichshowsthatprimalitytesting is of polynomial time. In algebraic number theory there is a complete presentation of primes and prime factorizations in algebraic number ?elds.

### What people are saying -Write a review

User Review - Flag as inappropriate

I was disappointed by this book overall, but especially the proofs. Many were jumpy and hard to follow, not clearly explaining what was going on. Some left out important truth conditions, and several had fatal typos that made the math impossible to follow. The whole text seemed like it had been rushed to the printer without thorough editing or review. The 2nd edition will hopefully be better.

User Review - Flag as inappropriate

good phi

### Contents

 Introduction and Historical Remarks 1 Basic Number Theory 6 22 Divisibility Primes and Composites 11 23 The Fundamental Theorem of Arithmetic 16 24 Congruences and Modular Arithmetic 21 241 Basic Theory of Congruences 22 242 The Ring of Integers Modulo n 23 243 Units and the Euler Phi Function 26
 47 Some Extensions and Comments 185 Primality Testing An Overview 197 52 Sieving Methods 198 521 Bruns Sieve and Bruns Theorem 204 53 Primality Testing and Prime Records 212 531 Pseudoprimes and Probabilistic Testing 218 532 The LucasLehmer Test and Prime Records 225 533 Some Additional Primality Tests 231

 244 Fermats Little Theorem and the Order of an Element 31 245 On Cyclic Groups 34 25 The Solution of Polynomial Congruences Modulo m 37 252 HigherDegree Congruences 42 26 Quadratic Reciprocity 45 The Inﬁnitude of Primes 55 312 Some Analytic Proofs and Variations 58 313 The Fermat and Mersenne Numbers 61 314 The Fibonacci Numbers and the Golden Section 65 315 Some Simple Cases of Dirichlets Theorem 78 316 A Topological Proof and a Proof Using Codes 83 32 Sums of Squares 86 321 Pythagorean Triples 87 322 Fermats TwoSquare Theorem 89 323 The Modular Group 94 324 Lagranges FourSquare Theorem 100 325 The Infinitude of Primes Through Continued Fractions 102 33 Dirichlets Theorem 104 34 Twin Prime Conjecture and Related Ideas 121 35 Primes Between x and 2x 122 36 Arithmetic Functions and the M�bius Inversion Formula 123 The Density of Primes 133 42 Chebychevs Estimate and Some Consequences 136 43 Equivalent Formulations of the Prime Number Theorem 149 44 The Riemann Zeta Function and the Riemann Hypothesis 157 441 The Real Zeta Function of Euler 158 442 Analytic Functions and Analytic Continuation 163 443 The Riemann Zeta Function 166 45 The Prime Number Theorem 173 46 The Elementary Proof 180
 54 Cryptography and Primes 234 541 Some NumberTheoretic Cryptosystems 237 542 Public Key Cryptography and the RSA Algorithm 240 55 The AKS Algorithm 243 Primes and Algebraic Number Theory 252 62 Unique Factorization Domains 255 621 Euclidean Domains and the Gaussian Integers 261 622 Principal Ideal Domains 268 623 Prime and Maximal Ideals 272 63 Algebraic Number Fields 275 631 Algebraic Extensions of Q 282 632 Algebraic and Transcendental Numbers 284 633 Symmetric Polynomials 287 634 Discriminant and Norm 290 64 Algebraic Integers 294 641 The Ring of Algebraic Integers 296 642 Integral Bases 297 643 Quadratic Fields and Quadratic Integers 300 644 The Transcendence of e and π 303 Minkowski Theory 306 646 Dirichlets Unit Theorem 308 65 The Theory of Ideals 311 651 Unique Factorization of Ideals 313 652 An Application of Unique Factorization 319 653 The Ideal Class Group 321 654 Norms of Ideals 323 655 Class Number 326 Bibliography and Cited References 333 Index 337 Copyright

### Popular passages

Page 10 - A then k + 1 e A. It can be concluded that in this case, A = N. This generalization provides the basis for proof by mathematical induction. The corresponding theorem is as follows: If for a given statement about positive integers, the statement is true for 1 and if it is true for n = k, then it is true for n = k + 1 , then the statement is true for all positive integers.