In mathematics, a prime number, or prime for short, is a natural number greater than one and whose only distinct positive divisors are 1 and itself. A natural number that is greater than one and is not a prime is called a composite number. A prime number has exactly two divisors. The numbers 0 and 1 are neither prime nor composite; note that 1 has only one divisor; a factor of 1 is of no interest in any product. The property of being a prime is called primality. Prime numbers are of fundamental importance in number theory.

The sequence of prime numbers begins

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 ...

(This is sequence A000040 [1] in OEIS; see list of prime numbers for the first 500 primes.) The set of all prime numbers is sometimes denoted by ℙ, a blackboard bold P. As 2 is the only even prime number, the term odd prime is used to refers to all prime numbers except 2.

In the context of ring theory, a branch of abstract algebra, the term "prime element" has a specific meaning. Here, a ring element a is defined to be prime if whenever a divides bc for ring elements b and c, then a divides one of b or c. With this meaning, the additive inverse of any prime number is also prime. In other words, when considering the set of integers Z as a ring, −7 is a prime element. However, even among mathematicians, the term "prime number" generally means a positive prime integer.

Representing natural numbers as products of primes

The fundamental theorem of arithmetic states that every positive integer can be written as a product of primes, and in essentially only one way. Primes are thus the "basic building blocks" of the natural numbers. For example, we can write

See prime factorization algorithm for details for how to do this in practice, for larger numbers.

The importance of this theorem is one of the reasons for the exclusion of 1 from the set of prime numbers. If 1 were admitted as a prime, the precise statement of the theorem would require additional qualifications.

• Numbers all of whose prime factors are the same are prime powers.
• Numbers with exactly three prime factors are sphenic numbers.
• Numbers with many divisors are highly composite numbers

How many prime numbers are there?

There are infinitely many prime numbers. The oldest known proof for this statement is given by the Greek mathematician Euclid in his Elements (Book IX, Proposition 20). Euclid states the result as "there are more than any given [finite] number of primes", and his proof can be briefly summarized as follows:

Take a finite number of primes, which we will assume to be all existing primes for the sake of argument. Multiply them all together and add one (see Euclid number). The resulting number is not divisible by any of the finite set of primes, because dividing by any of these would give a remainder of one. Therefore it must either be prime itself, or be divisible by some other prime that was not included in the finite set. Therefore the set we started with was not in fact all primes.

Other mathematicians have given their own proofs. One of those (due to Euler) shows that the sum of the reciprocals of all prime numbers diverges to infinity. Kummer's is particularly elegant and Furstenberg provides one using general topology.

Even though the total number of primes is infinite, one could still ask "how many primes are there below 100,000" or "How likely is a random 100-digit number to be prime?" Questions like these are answered by the prime number theorem.

Finding prime numbers

The Sieve of Eratosthenes is a simple way to compute the list of all prime numbers up to a given limit.

In practice though, one usually wants to check if a given number is prime, rather than generate a list of primes. Further, it is often satisfactory to know the answer with a high probability. It is possible to quickly check whether a given large number (say, up to a few thousand digits) is prime using probabilistic primality tests. These typically pick a random number called a "witness" and check some formula involving the witness and the potential prime N. After several iterations, they declare N to be "definitely composite" or "probably prime". These tests are not perfect. For a given test, there may be some composite numbers that will be declared "probably prime" no matter what witness is chosen. Such numbers are called pseudoprimes for that test.

A new deterministic algorithm which finds whether a given number N is prime and which uses time polynomial in the number of digits of N has recently been described.

Some properties of primes

• If p is a prime number and p divides a product ab of integers, then p divides a or p divides b. This proposition was proved by Euclid and is known as Euclid's lemma. It is used in some proofs of the uniqueness of prime factorizations.
• The ring Z/nZ (see modular arithmetic) is a field if and only if n is a prime. Put another way: n is prime if and only if φ(n) = n − 1.
• If p is prime and a is any integer, then a^p − a is divisible by p (Fermat's little theorem).
• If p is a prime number other than 2 and 5, 1/p is always a recurring decimal, with a period of p-1 or a divisor of p-1. This can be deduced directly from Fermat's little theorem. 1/p expressed likewise in base q (i.e. other than base 10) has similar effect, provided that p is not a prime factor of q. The Wiki page on recurring decimal shows some of the interesting properties.
• An integer p > 1 is prime if and only if the factorial (p − 1)! + 1 is divisible by p (Wilson's theorem). Conversely, an integer n > 4 is composite if and only if (n − 1)! is divisible by n.
• If n is a positive integer, then there is always a prime number p with n < p ≤ 2n (Bertrand's postulate).
• Adding the reciprocals of all primes together results in a divergent infinite series (proof). More precisely, if S(x) denotes the sum of the reciprocals of all prime numbers p with p ≤ x, then S(x) = Θ(ln ln x) for x → ∞ (see Big O notation).
• For each prime number p > 2, there exists a natural number n such that p = 4n ± 1.
• For each prime number p > 3, there exists a natural number n such that p = 6n ± 1.
• In every arithmetic progression a, a + q, a + 2q, a + 3q,... where the positive integers a and q ≥ 1 are coprime, there are infinitely many primes (Dirichlet's theorem).
• The characteristic of every field is either zero or a prime number.
• If G is a finite group and pⁿ is the highest power of the prime p which divides the order of G, then G has a subgroup of order pⁿ. (Sylow theorems)
• If p is prime and G is a group with pⁿ elements, then G contains an element of order p.
• The prime number theorem says that the number of primes less than x is asymptotic to x/(ln x).

Open questions

There are many open questions about prime numbers. For example:

• Goldbach's conjecture: Can every even integer greater than 2 be written as a sum of two primes?
• Twin Prime Conjecture: A twin prime is a pair of primes with difference 2, such as 11 and 13. Are there infinitely many twin primes?
• Does the Fibonacci sequence contain an infinite number of primes?
• Are there infinitely many Mersenne primes and Fermat primes?
• Is there always a prime number between n² and (n + 1)² for every n?
• Are there infinitely many primes of the form n² + 1?
• Prime Structure : What is the structure of prime numbers ?
• Riemann hypothesis: The zeros of the Riemann zeta function and the prime numbers satisfy a duality property which shows that the zeros of the zeta function can be regarded as the harmonic frequencies in the distribution of primes. Is the hypothesis, "the non-trivial zeros lie on the critical line 1/2," true of all non-trivial zeros?

The largest known prime

The largest known prime is 2^25964951 − 1 (this number is 7,816,230 digits long); it is the 42nd known Mersenne prime. M_25964951 was found on February 18, 2005 by Martin Nowak, a member of a collaborative effort known as GIMPS).

The next largest known prime is 2^24036583 − 1 (this number is 7,235,733 digits long); it is the 41st known Mersenne prime. M_24036583 was found on May 15, 2004 by Josh Findley (member of GIMPS) and it was announced in late May 2004.

The third largest known prime is 2^20996011 − 1 (this number is 6,320,430 digits long); it is the 40th known Mersenne prime. M_20996011 was found on November 17, 2003 by Michael Shafer (and GIMPS) and announced in early December 2003.

Historically, the largest known prime has almost always been a Mersenne prime since the dawn of electronic computers, because there exists a particularly fast primality test for numbers of this form, the Lucas-Lehmer test.

Some of the largest primes not known to have any particular form (that is, no simple formula such as that of Mersenne primes) have been found by taking a piece of semi-random binary data, converting it to a number n, multiplying it by 256^k for some positive integer k, and searching for possible primes within the interval [256^kn + 1, 256^k(n + 1) − 1].

In fact, as a publicity stunt against the Digital Millennium Copyright Act and other WIPO Copyright Treaty implementations, some people have applied this to various forms of DeCSS code, creating the set of illegal prime numbers. Such numbers, when converted to binary and executed as a computer program, perform acts encumbered by applicable law in one or more jurisdictions.

Applications

Extremely large prime numbers (that is, greater than 10¹⁰⁰) are used in several public key cryptography algorithms. Primes are also used for hash tables and pseudorandom number generators.

Primality tests

Main article primality test

A primality test algorithm is an algorithm which tests a number for primality, i.e. whether the number is a prime number.

• AKS primality test
• Fermat primality test
• Lucas-Lehmer test
• Lucas-Lehmer primality test
• Solovay-Strassen primality test
• Miller-Rabin primality test

Some special types of primes

A prime p is called primorial or prime-factorial if it has the form p = Π(n) ± 1 for some number n, where Π(n) stands for the product 2 · 3 · 5 · 7 · 11 · ... of all the primes ≤ n. A prime is called factorial if it is of the form n! ± 1. The first factorial primes are:

n! − 1 is prime for n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166,...

n! + 1 is prime for n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154... (sequence A002981 in OEIS)

The largest known primorial prime is Π(24029) + 1, found by Caldwell in 1993. The largest known factorial prime is 3610! − 1 [Caldwell, 1993]. It is not known if there are infinitely many primorial or factorial primes.

Primes of the form 2ⁿ − 1 are known as Mersenne primes, while primes of the form are known as Fermat primes. Prime numbers p where 2p + 1 is also prime are known as Sophie Germain primes. Other special types of prime numbers include Wieferich primes, Wilson primes, Wall-Sun-Sun primes, Wolstenholme primes, unique primes, Newman-Shanks-Williams primes (NSW primes), Smarandache-Wellin primes, Wagstaff primes and supersingular primes.

The base-ten digit sequence of a prime can be a palindrome, as in the prime 10³¹⁵¹² + 9700079 · 10¹⁵⁷⁵³ + 1.

Prime gaps

Let p_n denote the n-th prime number (i.e. p₁ = 2, p₂ = 3, etc.). The gap g_n between the consecutive primes p_n and p_{n + 1} is the number of (composite) numbers between them, i.e.

g_n = p_{n + 1} − p_n − 1.

(Slightly different definitions are sometimes used.) We have g₁ = 0, g₂ = g₃ = 1, and g₄ = 3. The sequence {g_n} of prime gaps has been extensively studied.

For any N, the sequence

(N + 1)! + 2, (N + 1)! + 3, ..., (N + 1)! + N + 1

is a sequence of N consecutive composite integers. Therefore, there exist gaps between primes which are arbitrarily large, i.e. for any natural number N, there is an integer n with g_n > N. (Choose n so that p_n is the greatest prime number less than (N + 1)! + 2.) On the other hand, the gaps get arbitrarily small in proportion to the primes: the quotient (g_n/p_n) approaches zero as n approaches infinity.

We say that g_n is a maximal gap if g_m < g_n 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.

The largest prime gap with identified gap ends known as of 1 January 2005 has a length of 2254930. See: http://hjem.get2net.dk/jka/math/primegaps/megagap2.htm

Note that the Twin Prime Conjecture simply asserts that g_n = 1 for infinitely many integers n.

Formulae yielding prime numbers

Main article formula for primes

There is no formula for primes which is more efficient at finding primes than the methods mentioned above under "Finding prime numbers". Those which do exist have little practical value.

The curious polynomial f(n) = n² − 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.

There is a set of diophantine equations in 25 variables and one parameter with the following property: the parameter is prime if and only if the resulting system of equations has a solution over the natural numbers. This can be used to obtain a single formula with the property that all its positive values are prime.

Another formula is based on Wilson's theorem mentioned above, and generates the number two many times and all other primes exactly once. There are other similar formulae which also produce primes.

Generalizations

The concept of prime number is so important that it has been generalized in different ways in various branches of mathematics.

In number theory itself, one talks of "probable primes", integers which, by virtue of having passed a certain test, are considered to be probably prime. Probable primes which are in fact composite (such as Carmichael numbers) are called pseudoprimes.

One can define prime elements and irreducible elements in any integral domain. For the ring of integers, the set of prime elements equals the set of irreducible elements; it's {...−11, −7, −5, −3, −2, 2, 3, 5, 7, 11, ...}.

As another example, we can extend the integers to the Gaussian integers Z[i], that is, complex numbers of the form a + bi with a and b in Z. This is an integral domain, and its prime elements are the Gaussian primes. Note that 2 is not a Gaussian prime, because it factors into the product of the two Gaussian primes (1 + i) and (1 − i). The element 3, however, remains prime even in the Gaussian integers. In general, rational primes (i.e. prime elements in the ring of integers) of the form 4k + 3 are Gaussian primes, whereas rational primes of the form 4k + 1 are not.

In ring theory, one generally replaces the notion of number with that of ideal. Prime ideals are an important tool and object of study in commutative algebra, algebraic number theory and algebraic geometry. The prime ideals of the ring of integers are the ideals (0), (2), (3), (5), (7), (11), ...

In class field theory yet another generalization is used. Given an arbitrary field K, one considers valuations on K, certain functions from K to the real numbers R. Every such valuation yields a topology on K, and two valuations are called equivalent if they yield the same topology. A prime of K is an equivalence class of valuations. With this definition, the primes of the field Q of rational numbers are represented by the standard absolute value function (known as the "infinite prime") as well as by the p-adic valuations on Q, for every prime number p.

Quotes

"Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate." — Leonhard Euler

"God may not play dice with the universe, but something strange is going on with the prime numbers." — Paul Erdős

See also

• Prime power
• Sphenic number
• Highly composite number
• Primorial

References

• Karl Sabbagh, The Riemann Hypothesis: The Greatest Unsolved Problem in Mathematics. Farrar, Straus and Giroux; 340 pages
• John Derbyshire, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. Joseph Henry Press; 448 pages
• Marcus du Sautoy, The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics. HarperCollins; 352 pages
• H. Riesel, Prime Numbers and Computer Methods for Factorization, 2nd ed., Birkhäuser 1994.

External links

• Prime curios at the prime pages
• The prime pages -- http://www.utm.edu/research/primes/
• MacTutor history of prime numbers
• The "PRIMES is in P" FAQ
• The first 20,000 primes (through 224737) at Wikisource
• List of largest known probable primes
• The prime puzzles
• The Prime Project generates a new prime number every time the page is loaded
• An English translation of Euclid's proof that there are infinitely many primes
• Primes from WIMS is an online prime generator.
• Prime Factorization Worksheet generates new questions every time the page is loaded
• Prime Spiral pattern
• 12 digit primes Known 12-digit prime factors of Googolplex - 1