What Is Number Theory?

1 The Integers

1.1 Numbers and Sequences

1.2 Sums and Products

1.3 Mathematical Induction

1.4 The Fibonacci Numbers

1.5 Divisibility

2 Integer Representations and Operations

2.1 Representations of Integers

2.2 Computer Operations with Integers

2.3 Complexity of Integer Operations

3 Primes and Greatest Common Divisors

3.1 Prime Numbers

3.2 The Distribution of Primes

3.3 Greatest CommonDivisors

3.4 The Euclidean Algorithm

3.5 The Fundamental Theorem of Arithmetic

3.6 Factorization Methods and the Fermat Numbers

3.7 Linear Diophantine Equations

4 Congruences

4.1 Introduction to Congruences

4.2 Linear Congruences

4.3 The Chinese Remainder Theorem

4.4 Solving Polynomial Congruences

4.5 Systems of Linear Congruences

4.6 Factoring Using the Pollard Rho Method

5 Applications of Congruences

5.1 Divisibility Tests

5.2 The Perpetual Calendar

5.3 Round-Robin Tournaments

5.4 Hashing Functions

5.5 Check Digits

6 Some Special Congruences

6.1 Wilson's Theorem and Fermat's Little Theorem

6.2 Pseudoprimes

6.3 Euler's Theorem

7 Multiplicative Functions

7.1 The Euler Phi-Function

7.2 The Sum and Number of Divisors

7.3 Perfect Numbers and Mersenne Primes

7.4 M？bius Inversion

8 Cryptology

8.1 Character Ciphers

8.2 Block and Stream Ciphers

8.3 Exponentiation Ciphers

8.4 Public Key Cryptography

8.5 Knapsack Ciphers

8.6 Cryptographic Protocols and Applications

9 Primitive Roots

9.1 The Order of an Integer and Primitive Roots

9.2 Primitive Roots for Primes

9.3 The Existence of Primitive Roots

9.4 Index Arithmetic

9.5 Primality Tests Using Orders of Integers and Primitive Roots

9.6 Universal Exponents

10 Applications of Primitive Roots and the Order of an Integer

10.1 Pseudorandom Numbers

10.2 The ElGamal Cryptosystem

10.3 An Application to the Splicing of Telephone Cables

11 Quadratic Residues

11.1 Quadratic Residues and Nonresidues

11.2 The Law of Quadratic Reciprocity

11.3 The Jacobi Symbol

11.4 Euler Pseudoprimes

11.5 Zero-Knowledge Proofs

12 Decimal Fractions and Continued Fractions

12.1 Decimal Fractions

12.2 Finite Continued Fractions

12.3 Infinite Continued Fractions

12.4 Periodic Continued Fractions

12.5 Factoring Using Continued Fractions

13 Some Nonlinear Diophantine Equations

13.1 Pythagorean Triples

13.2 Fermat's Last Theorem

13.3 Sums of Squares

13.4 Pell's Equation

14 The Gaussian Integers

14.1 Gaussian Integers and Gaussian Primes

14.2 Greatest Common Divisors and Unique Factorization

14.3 Gaussian Integers and Sums of Squares

A Axioms for the Set of Integers

B Binomial Coefficients

C Using Maple and Mathematica for Number Theory

C.1 Using Maple forNumberTheory

C.2 Using Mathematica for Number Theory

D Number Theory Web Links

E Tables

Answers to Odd-Numbered Exercises

Bibliography

Index of Biographies

Index

Photo Credits