All you wanted to know about primes

Prime numbers

Introduction

More and more people are becoming interested in primes numbers. However, not everyone has a background in mathematics, or in the particular branches of mathematics that prime numbers inhabit. This means that what sometimes appears obvious or trivial to one person, is sometimes a fascinating revelation to another. There is also a big difference between differing viewpoints on what constitutes real mathematics and what is an irrelevant side issue. I certainly cannot change peoples' views, and of course my own views may be an acquired taste, but I hope in the following to give enough background information, and where to go to find even more, that will be if use to as many people as possible.

This site is not strictly an FAQ, but I hope that anyone with a question will be able to find an answer or a suggestion on where to find one, or even a suggestion on how to find out for yourself. The structure is a follows:

Section 1 - Fundamentals

This contains most of the standard arithmetic concepts that are used throughout number theory, including what ideas we can presuppose (and I presuppose very little), and then moving on to the Division Algorithm, Greatest Common Divisor, Congruences, and finishing with the Chinese Remainder Theorem.

Section 2 - Primes - The Basics

This contains the classical results regarding primes, including the Fundamental Theorem of Arithmetic, describes the Sieve of Eratosthenes and Trial Division, and then introduces some more standard theory about primes using the results from Section 1, including Fermat's Little Theorem and Euler's generalisation, using the Euler phi-function. I finish by introducing the idea of primitive roots.

Section 3 - Frequency of Primes

Here, I introduce quadratic residues and the Legendre symbol in order to prove some simple results about primes of certain forms. I then move on to looking at counting primes, including a look at prime gaps, twin primes, Sophie-Germain primes, and primes in more general arithmetic progressions. This section includes a scattering of interesting conjectures.

Section 4 - Primes - Primality Proofs

In this section, I give some of the simpler, but very much still useful, primality proofs that are based on the factorisation of n- 1 or n+1, where n is the number being considered. This includes the standard tests of Lucas, Lehmer, Proth, Pocklington, Brillhart-Lehmer-Selfridge etc. and goes on to provide a bit of Lucasian theory.

Section 5 - Special Types of Primes

Here, I consider numbers of specific forms such as Fermat Numbers and Mersenne primes, including particular primality proofs and restrictions on divisors. I also include various other formulae such as n!+1, n² + n + a, etc, and then introduce some additive concepts, including the famous Goldbach conjecture. This section mentions lots of other interesting conjectures.

Section 6 - Numbers of the form k*2ⁿ ± 1

All numbers can be expressed in this form, with k odd. However by considering them specifically in this way, a lot of modular results can be obtained that can help us to find restrictions to our searches. This section includes an introduction to the Nash sieve and its variants, Sierpinski, Riesel and Brier numbers, Keller cycles and flip cycles. This is also a convenient place to mention Cunningham chains and bi-chains.

Section 7 - Advanced Primality Tests

For numbers that don't fit into any convenient pattern, there are more general primality tests available. These are usually more complicated mathematically than the specific ones already presented, so full proofs can't be given here, but I do try to give you a flavour for them, and it is well worth knowing how they arise from the theory.

References

Textbooks that I thoroughly recommend are the following :

Elementary Number Theory, David M. Burton, Allyn & Bacon, Revised Printing.
Introduction to Analytic Number Theory, Tom M. Apostol, Springer-Verlag, UTM.
The New Book of Prime Number Records, Paulo Ribenboim, Springer-Verlag.

In addition, the text is littered with hyperlink references, which I repeat here in no particular order :

The Prime Page - Chris Caldwell's repository for all things prime-related.

The pi-x project - a collaborative effort to calculate p (x) for very large x.

Thomas Nicely - contains detailed lists of prime gaps and twin prime counts.

Carlos Rivera - part of Carlos Rivera's Prime Puzzles and Problems Cnnection website, contains various records connected to arithmetic progressions of primes.

Tony Forbes - website full of downloads and HTML pages, in particular relating to arithmetic progressions of primes and MFAC Fermat number factoring program

Yves Gallot's Proth - download proth.exe.

Fermat Search - Loenid Durman's collaborative effort to find factors of Fermat numbers.

Generalised Fermat Prime Search - Yves Gallot's collaborative effort.

GIMPS - George Woltman's collaborative effort.

Cunningham-Woodall Project - Sam Wagstaff collaborative factoring effort.

ECMNET - factoring effort maintained by Paul Zimmerman.

NFS@Home - factoring effort based at California State University Fullerton

YAFU - Yet another factorization Utility by Buhrow

Chris Nash' Psieve - download psieve.exe.

Henri Lifchitz - bi-twin and bi-chain records, download winbitwin.exe.

Henri & Renaud Lifchitz - Top 10000 list of Probable Primes

Proth Search - Ballinger & Keller's site dedicated to search for Proth primes.

Paul Jobling's Newpgen - download newpgen.exe.