Prime gaps
The gap between the n-th prime pn and the n+1-st prime pn+1 is defined to be the number of composite numbers between them, i.e. gn = pn+1 - pn - 1 (slightly different definitions are sometimes used).
We have g1 = 0 and g2 = 1.
The sequence (gn) of prime gaps has been extensively studied.
One can show that gaps get arbitrarily large, i.e. for any natural number N, there is an index n with gn > N. On the other hand, for any positive real number ε, there exists a start index n0 such that gn < ε · pn for all n > n0.
We say that gn is a maximal gap if gm < gn for all m < n. The largest known maximal gap is 1131, found by T. Nicely and B. Nyman in 1999. It is the 64th smallest maximal gap, and it occurs after the prime 1693182318746371.
Formulas yielding prime numbers
The curious polynomial f(n) = n2 - n + 41 yields primes for n = 0,..., 40, but f(41) is composite. There is no polynomial which only yields prime numbers in this
fashion, but a set of diophantine equations in 26 variables can be used to obtain primes: A given number k + 2 is prime iff the following system of diophantine equations has a solution in the natural numbers (Riesel, 1994):
-
-
-
-
-
-
-
-
-
-
-
-
-
The following function yields all the primes, and only primes, for natural numbers n:
-
This formula is based on Wilson's theorem mentioned above; two is generated many times and all other primes are generated exactly once by this function.
(In fact a prime p is generated for n=(p-1) and 2 otherwise (ie. when n+1 is composite))
Using the floor function [x] (defined to be the largest integer less than or equal to the real number x), one can construct several formulas for the n-th prime. These formulas are also based on Wilson's theorem and have little practical value: the methods mentioned above under "Finding prime numbers" are much more efficient.
Define
or, alternatively,
These definitions are equivalent; π(m) is the number of primes less than or equal to m. The n-th prime number pn can then be written as
Another approach does not use factorials and Wilson's theorem, but also heavily employs the floor function (S. M. Ruiz 2000): first define
-
and then
Generalizations
The concept of prime number is so important that it has been generalized in different ways in various branches of mathematics. The set {2,3,5,7,11,...} (sometimes denoted by a blackboard bold 'P', ) is the primes over the natural numbers. The set {...-11,-7,-5,-3,-2,2,3,5,7,11,...} is the primes over the integers. When the word prime or prime number is used without qualification in the Wikipedia, it means a prime natural number. This is a common definition, but some mathematics dictionaries define it instead to mean a prime integer.
In number theory itself, one talks of pseudoprimes, integers which, by virtue of having passed a certain test, are considered probable primes but are in fact composite (such as Carmichael numbers). To model some of the behavior of prime numbers, one defines prime and irreducible polynomials. More generally, one can define prime and irreducible elements in every integral domain. Prime ideals are an important tool and object of study in commutative algebra and algebraic geometry.
Primality tests
A primality test algorithm is an algorithm which tests a number for primality.