Preface Flowchart of Chapter Dependencies Introduction 1. What Is Number Theory? 2. Pythagorean Triples 3. Pythagorean Triples and the Unit Circle 4. Sums of Higher Powers and Fermat’s Last Theorem 5. Divisibility and the Greatest Common Divisor 6. Linear Equations and the Greatest Common Divisor 7. Factorization and the Fundamental Theorem of Arithmetic 8. Congruences 9. Congruences, Powers, and Fermat’s Little Theorem 10. Congruences, Powers, and Euler’s Formula 11. Euler’s Phi Function and the Chinese Remainder Theorem 12. Prime Numbers 13. Counting Primes 14. Mersenne Primes 15. Mersenne Primes and Perfect Numbers 16. Powers Modulo m and Successive Squaring 17. Computing kth Roots Modulo m 18. Powers, Roots, and “Unbreakable” Codes 19. Primality Testing and Carmichael Numbers 20. Squares Modulo p 21. Quadratic Reciprocity 22. Proof of Quadratic Reciprocity 23. Which Primes Are Sums of Two Squares? 24.Which Numbers Are Sums of Two Squares? 25. Euler’s Phi Function and Sums of Divisors 26. Powers Modulo p and Primitive Roots 27. Primitive Roots and Indices 28. The Equation X4 + Y4 = Z4 29. Square–Triangular Numbers Revisited 30. Pell’s Equation 31. Diophantine Approximation 32. Diophantine Approximation and Pell’s Equation 33. Number Theory and Imaginary Numbers 34. The Gaussian Integers and Unique Factorization 35. Irrational Numbers and Transcendental Numbers 36. Binomial Coefficients and Pascal’s Triangle 37. Fibonacci’s Rabbits and Linear Recurrence Sequences 38. Cubic Curves and Elliptic Curves 39. Elliptic Curves with Few Rational Points 40. Points on Elliptic Curves Modulo p 41. Torsion Collections Modulo p and Bad Primes 42. Defect Bounds and Modularity Patterns 43. Elliptic Curves and Fermat’s Last Theorem   Index   *47. The Topsy-Turvey World of Continued Fractions [online] *48. Continued Fractions, Square Roots, and Pell’s Equation [online] *49. Generating Functions [online] *50. Sums of Powers [online] *A. Factorization of Small Composite Integers [online] *B. A List of Primes [online]   *These chapters are available online

50 short chapters provide flexibility and options for instructors and students. A flowchart of chapter dependencies is included in this edition.Five basic steps are emphasized throughout the text to help readers develop a robust thought process: ExperimentationPattern recognitionHypothesis formationHypothesis testingFormal proofRSA cryptosystem, elliptic curves, and Fermat's Last Theorem are featured, showing the real-life applications of mathematics.

There are a number of major changes in the Fourth Edition. Many new exercises appear throughout the text.A flowchart giving chapter dependencies is included to help instructors choose the most appropriate mix of topics for their students.Content Updates There is a new chapter on mathematical induction (Chapter 26).Some material on proof by contradiction has been moved forward to Chapter 8. It is used in the proof that a polynomial of degree d has at most d roots modulo p. This fact is then used in place of primitive roots as a tool to prove Euler’s quadratic residue formula in Chapter 21. (In earlier editions, primitive roots were used for this proof.)The chapters on primitive roots (Chapters 28–29) have been moved to follow the chapters on quadratic reciprocity and sums of squares (Chapters 20–25). The rationale for this change is the author’s experience that students find the Primitive Root Theorem to be among the most difficult in the book. The new order allows the instructor to cover quadratic reciprocity first, and to omit primitive roots entirely if desired.Chapter 22 now includes a proof of part of quadratic reciprocity for Jacobi symbols, with the remaining parts included as exercises.Quadratic reciprocity is now proved in full. The proofs for (-1/p) and (2/p) remain as before in Chapter 21, and there is a new chapter (Chapter 23) that gives Eisenstein’s proof for (p/q)(q/p). Chapter 23 is significantly more difficult than the chapters that precede it, and it may be omitted without affecting the subsequent chapters.As an application of primitive roots, Chapter 28 discusses the construction of Costas arrays.Chapter 39 includes a proof that the period of the Fibonacci sequence modulo p divides p - 1 when p is congruent to 1 or 4 modulo 5.Number theory is a vast and sprawling subject, and over the years this book has acquired many new chapters. In order to keep the length of this edition to a reasonable size, Chapters 47, 48, 49, and 50 have been removed from the printed version of the book. These omitted chapters are freely available online at http://math.brown.edu/~jhs/frint.html or www.pearsonhighered.com/silverman. The online chapters are included in the index.