## Number Theory: An Introduction via the Distribution of PrimesNumber 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

1 | |

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 |

333 | |

337 | |

### Other editions - View all

### Common terms and phrases

abelian group algebraic integers algebraic number field analytic called Chapter Chebychev coefficients computational congruences conjecture conjugates consider contradiction converges Corollary cyclic defined Definition denote Dirichlet’s theorem divides division algorithm element equivalent Euclid’s Euclidean domain Euler pseudoprime example exercises exists finite follows formula fundamental theorem Further given Hence implies induction infinitely many primes integral domain integral ideal inverse irreducible Lemma Li(x linear combination log2 Mersenne primes mod q modulo multiplicative natural number nonzero norm number of primes odd prime positive integers primality testing prime divisor prime factorization prime ideals prime number theorem proof of Theorem prove quadratic residue quadratic residue mod rational integer Recall relatively prime residue classes result Riemann hypothesis Riemann zeta function sequence of primes solution square square-free Suppose symmetric polynomials theorem of arithmetic twin primes unique factorization von Mangoldt function zero

### 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.