Elementary Number Theory, 7e, by David M. Burton

Table of Contents

Preface

New to this Edition

1Preliminaries

1.1Mathematical Induction

1.2The Binomial Theorem

2Divisibility Theory in the Integers

2.1Early Number Theory

2.2The Division Algorithm

2.3The Greatest Common Divisor

2.4The Euclidean Algorithm

2.5The Diophantine Equation

3Primes and Their Distribution

3.1The Fundamental Theorem of Arithmetic

3.2The Sieve of Eratosthenes

3.3The Goldbach Conjecture

4The Theory of Congruences

4.1Carl Friedrich Gauss

4.2Basic Properties of Congruence

4.3Binary and Decimal Representations of Integers

4.4Linear Congruences and the Chinese Remainder Theorem

5Fermat’s Theorem

5.1Pierre de Fermat

5.2Fermat’s Little Theorem and Pseudoprimes

5.3Wilson’s Theorem

5.4The Fermat-Kraitchik Factorization Method

6Number-Theoretic Functions

6.1The Sum and Number of Divisors

6.2 The Möbius Inversion Formula

6.3The Greatest Integer Function

6.4An Application to the Calendar

7Euler’s Generalization of Fermat’s Theorem

7.1Leonhard Euler

7.2Euler’s Phi-Function

7.3Euler’s Theorem

7.4Some Properties of the Phi-Function

8Primitive Roots and Indices

8.1The Order of an Integer Modulo n

8.2Primitive Roots for Primes

8.3Composite Numbers Having Primitive Roots

8.4The Theory of Indices

9The Quadratic Reciprocity Law

9.1Euler’s Criterion

9.2The Legendre Symbol and Its Properties

9.3Quadratic Reciprocity

9.4Quadratic Congruences with Composite Moduli

10Introduction to Cryptography

10.1From Caesar Cipher to Public Key Cryptography

10.2The Knapsack Cryptosystem

10.3An Application of Primitive Roots to Cryptography

11Numbers of Special Form

11.1Marin Mersenne

11.2Perfect Numbers

11.3Mersenne Primes and Amicable Numbers

11.4Fermat Numbers

12Certain Nonlinear Diophantine Equations

12.1The Equation

12.2Fermat’s Last Theorem

13Representation of Integers as Sums of Squares

13.1Joseph Louis Lagrange

13.2Sums of Two Squares

13.3Sums of More Than Two Squares

14Fibonacci Numbers

14.1Fibonacci

14.2The Fibonacci Sequence

14.3Certain Identities Involving Fibonacci Numbers

15Continued Fractions

15.1Srinivasa Ramanujan

15.2Finite Continued Fractions

15.3Infinite Continued Fractions

15.4Farey Fractions

15.5Pell’s Equation

16Some Recent Developments

16.1Hardy, Dickson, and Erdös

16.2Primality Testing and Factorization

16.3An Application to Factoring: Remote Coin Flipping

16.4The Prime Number Theorem and Zeta Function

Miscellaneous Problems

Appendixes

General References

Suggested Further Reading

Tables

Answers to Selected Problems

Index