THE LITTLE BOOK OF BIGGER PRIMES
CONTENTS HOW MANY PRIME NUMBERS ARE THERE? I EUCLID’S PROOF II GOLDBACH DID IT TOO! III EULER’S PROOF IV THUE’S PROOF V THREE FORGOTTEN PROOFS A PEROTT’S PROOF B AURIC’S PROOF C M´ETROD’S PROOF VI WASHINGTON’S PROOF VII FURSTENBERG’S PROOF 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 AND OF WOLSTENHOLME D THE POWER OF A PRIME DIVIDING A FACTORIAL E THE CHINESE REMAINDER THEOREM F EULER’S FUNCTION G SEQUENCES OF BINOMIALS H QUADRATIC RESIDUES III CLASSICAL PRIMALITY TESTS BASED ON CONGRUENCES IV LUCAS SEQUENCES V PRIMALITY TESTS BASED ON LUCAS SEQUENCES VI FERMAT NUMBERS VII MERSENNE NUMBERS VIII PSEUDOPRIMES A PSEUDOPRIMES IN BASE 2 (PSP) B PSEUDOPRIMES IN BASE A (PSP(A)) C EULER PSEUDOPRIMES IN BASE A (EPSP(A)) D STRONG PSEUDOPRIMES IN BASE A (SPSP(A)) IX CARMICHAEL NUMBERS X LUCAS PSEUDOPRIMES A FIBONACCI PSEUDOPRIMES B LUCAS PSEUDOPRIMES (LPSP(P, Q)) C EULER-LUCAS PSEUDOPRIMES (ELPSP(P, Q)) AND STRONG LUCAS PSEUDOPRIMES (SLPSP(P, Q)) D CARMICHAEL–LUCAS NUMBERS XI PRIMALITY TESTING AND FACTORIZATION A THE COST OF TESTING B MORE PRIMALITY TESTS C TITANIC AND CURIOUS PRIMES D FACTORIZATION E PUBLIC KEY CRYPTOGRAPHY ARE THERE FUNCTIONS DE?NING PRIME NUMBERS? I FUNCTIONS SATISFYING CONDITION (A) II FUNCTIONS SATISFYING CONDITION (B) III PRIME-PRODUCING POLYNOMIALS A PRIME VALUES OF LINEAR POLYNOMIALS B ON QUADRATIC FIELDS C PRIME-PRODUCING QUADRATIC POLYNOMIALS D THE PRIME VALUES AND PRIME FACTORS RACES IV FUNCTIONS SATISFYING CONDITION (C) HOW ARE THE PRIME NUMBERS DISTRIBUTED? I THE FUNCTION ?(X) A HISTORY UNFOLDING B SUMS INVOLVING THE M¨OBIUS FUNCTION C TABLES OF PRIMES D THE EXACT VALUE OF ?(X) AND COMPARISON WITH X/ LOG X, LI(X), AND R(X) E THE NONTRIVIAL ZEROS OF ?(S) F ZERO-FREE REGIONS FOR ?(S) AND THE ERROR TERM IN THE PRIME NUMBER THEOREM G SOME PROPERTIES OF ?(X) H THE DISTRIBUTION OF VALUES OF EULER’S FUNCTION II THE NTH PRIME AND GAPS BETWEEN PRIMES A THE NTH PRIME B GAPS BETWEEN PRIMES III TWIN PRIMES IV PRIME K-TUPLETS V PRIMES IN ARITHMETIC PROGRESSION A THERE ARE IN?NITELY MANY! B THE SMALLEST PRIME IN AN ARITHMETIC PROGRESSION C STRINGS OF PRIMES IN ARITHMETIC PROGRESSION VI GOLDBACH’S FAMOUS CONJECTURE VII THE DISTRIBUTION OF PSEUDOPRIMES AND OF CARMICHAEL NUMBERS A DISTRIBUTION OF PSEUDOPRIMES B DISTRIBUTION OF CARMICHAEL NUMBERS C DISTRIBUTION OF LUCAS PSEUDOPRIMES WHICH SPECIAL KINDS OF PRIMES HAVE BEEN CONSIDERED? I REGULAR PRIMES II SOPHIE GERMAIN PRIMES III WIEFERICH PRIMES IV WILSON PRIMES V REPUNITS VI NUMBERS K × BN ± VII PRIMES AND SECOND-ORDER LINEAR RECURRENCE SEQUENCES HEURISTIC AND PROBABILISTIC RESULTS ABOUT PRIME NUMBERS I PRIME VALUES OF LINEAR POLYNOMIALS II PRIME VALUES OF POLYNOMIALS OF ARBITRARY DEGREE III POLYNOMIALS WITH MANY SUCCESSIVE COMPOSITE VALUES IV PARTITIO NUMERORUM CONCLUSION