内容

目次

1. How Many Prime Numbers Are There?.- I. Euclid’s Proof.- II. Kummer’s Proof.- III. Pólya’s Proof.- IV. Euler’s Proof.- V. Thue’s Proof.- VI. Two-and-a-Half Forgotten Proofs.- A. Perott’s Proof.- B. Auric’s Proof.- C. Métrod’s Proof.- VII. Washington’s Proof.- VIII. Fürstenberg’s Proof.- 2. How to Recognize Whether a Natural Number Is a Prime?.- I. The Sieve of Eratosthenes.- II. Some Fundamental Theorems on Congruences.- A. Fermat’s Little Theorem and Primitive Roots Modulo a Prime.- B. The Theorem of Wilson.- C. The Properties of Giuga, Wolstenholme and Mann & Shanks.- D. The Power of a Prime Dividing a Factorial.- E. The Chinese Remainder Theorem.- F. Euler’s Function.- G. Sequences of Binomials 31.- H. Quadratic Residues.- III. Classical Primality Tests Based on Congruences.- IV. Lucas Sequences.- Addendum on Lehmer Numbers.- V. Classical Primality Tests Based on Lucas Sequences.- VI. Fermat Numbers.- VII. Mersenne Numbers.- Addendum on Perfect Numbers.- VIII. Pseudoprimes.- A. Pseudoprimes in Base 2 (psp).- B. Pseudoprimes in Base a (psp(a)).- B. Euler Pseudoprimes in Base a (epsp(a)).- D. Strong Pseudoprimes in Base a (spsp(a)).- Addendum on the Congruence an-k ? bn-k (mod n).- Carmichael Numbers.- Addendum on Knödel Numbers.- X. Lucas Pseudoprimes.- A. Fibonacci Pseudoprimes.- B. Lucas Pseudoprimes (e psp(P, Q)).- C. Euler—Lucas Pseudoprimes (e e psp(P, Q)) and Strong Lucas Pseudoprimes (s psp(P, Q)).- D. Carmichael—Lucas Numbers.- XI. Last Section on Primality Testing and Factorization!.- A. The Cost of Testing.- B. Recent Primality Tests.- C. Monte Carlo Methods.- D. Titanic Primes.- E. Factorization.- F. Public Key Cryptography.- 3. Are There Functions Defining Prime Numbers?.- I. Functions Satisfying Condition (a).- II. Functions Satisfying Condition (b).- III. Functions Satisfying Condition (c).- 4. How Are the Prime Numbers Distributed?.- I. The Growth of ?(x).- A. History Unfolding.- Euler.- Legendre.- Gauss.- Tschebycheff.- Riemann.- de la Valleé Poussin and Hadamard.- Erdös and Selberg.- B. Sums Involving the Möbius Function.- C. The Distribution of Values of Euler’s Function.- D. Tables of Primes.- E. The Exact Value of ?(x) and Comparison with x/(log x), Li(x), and R(x).- F. The Nontrivial Zeroes of ?(s).- G. Zero-Free Regions for ?(s) and the Error Term in the Prime Number Theorem.- H. The Growth of ?(s).- II. The nth Prime and Gaps.- A. Some Properties of ?(x).- B. The nth Prime.- C. Gaps between Primes.- D. The Possible Gaps between Primes.- E. Interlude.- III. Twin Primes.- Addendum on Polignac’s Conjecture.- IV. Primes in Arithmetic Progression.- A. There Are Infinitely Many!.- B. The Smallest Prime in an Arithmetic Progression.- C. Strings of Primes in Arithmetic Progression.- V. Primes in Special Sequences.- VI. Goldbach’s Famous Conjecture.- VII. The Waring-Goldbach Problem.- A. Waring’s Problem.- B. The Waring-Goldbach Problem.- VIII. The Distribution of Pseudoprimes and of Carmichael Numbers.- A. Distribution of Pseudoprimes.- B. Distribution of Carmichael Numbers.- C. Distribution of Lucas Pseudoprimes.- 5. Which Special Kinds of Primes Have Been Considered?.- I. Regular Primes.- II. Sophie Germain Primes.- III. Wieferich Primes.- IV. Wilson Primes.- V. Repunits and Similar Numbers.- VI. Primes with Given Initial and Final Digits.- VII. Numbers k × 2’ ± 1.- Addendum on Cullen Numbers.- VIII. Primes and Second-Order Linear Recurrence Sequences.- IX. The NSW-Primes.- 6. Heuristic and Probabilistic Results About Prime Numbers.- I. Prime Values of Linear Polynomials.- II. Prime Values of Polynomials of Arbitrary Degree.- III. Some Probabilistic Estimates.- A. Partitio Numerorum.- B. Polynomials with Many Successive Composite Values.- C. Distribution of Mersenne Primes.- D. The log log Philosophy.- IV. The Density of the Set of Regular Primes.- Conclusion.- Dear Reader:.- Citations for Some Possible Prizes for Work on the Prime Number Theorem.- A. General References.- B. Specific References.- 1.- 2.- 3.- 4.- 5.- 6.- Conclusion.- Primes up to 10,000.- Index of Names.- Gallimawfries.