In mathematics, a **prime number**, or **prime** for short, is a natural number larger than 1 that has as its only positive divisors (factors) 1 and itself. The first 25 prime numbers are

This definition is used throughout the Wikipedia. See the

*Generalizations*section, below, for another definition in common use. The property of being a prime is called

**primality**. If a number greater than one is not a prime number, it is called a composite number.

## Representing natural numbers as products of primes

An important fact is the fundamental theorem of arithmetic, which states that every natural number 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

- .

## 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. Multiply them all together and add one. 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 be divisible by some prime that was not included in the finite set.

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. Here's a description of the Fermat primality test.

A new algorithm which determines 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**_{n}(see modular arithmetic) is a field if and only if*n*is a prime. - The characteristic of every field is either zero or a prime number.
- If
*p*is prime and*a*is any integer, then*a*^{p}-*a*is divisible by*p*(Fermat's little theorem). - If
*G*is a finite group and*p*^{n}is the highest power of the prime*p*which divides the order of*G*, then*G*has a subgroup of order*p*^{n}. (Sylow theorems) - If
*p*is prime and*G*is a group with*p*^{n}elements, then*G*contains an element of order*p*. - 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*≤ 2*n*(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 the prime number ≤*x*, then*S*(*x*) = Θ(ln(ln(*x*))) for*x*→ ∞ (see Big O notation). - For each prime number
*p*> 3, there exists a natural number*n*such that*p*= 6*n*- 1 or*p*= 6*n*+ 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).

## Open Questions

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

- Goldbach's conjecture: Can every positive 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 Fermat primes?
- Is there always a prime number between
*n*^{2}and (*n*+ 1)^{2}for every*n*? - Are there infinitely many primes of the form
*n*^{2}+ 1?

## The largest known prime

The 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 a collaborative effort known as GIMPS and announced in early December 2003.

The next largest known prime is 2^{13466917}-1 (this number is 4,053,946 digits long). It is the 39th known Mersenne prime M_{13466917} also found by GIMPS on November 14 2001 and announced in early December 2001 after double checking. 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^{k}`n` + 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^{100}) are used in several public key cryptography algorithms. Primes are also used for hash tables and pseudorandom number generators.

## Some special types of primes

- 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, 13, 27, 37, 41, 73, 77, 116, 154...

Primes of the form 2^{n}-1 are known as Mersenne primes, while primes of the form 2^{2n}+1 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 and Newman-Shanks-Williams primes (NSW primes).

The base-ten digit sequence of a prime can be a palindrome, as in the prime 10^{31512} + 9700079 · 10^{15753} + 1.

## Prime gaps

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.

## Formulas yielding prime numbers

The curious polynomial *f*(*n*) = *n*^{2} - *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):

*n*:

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

*m*) is the number of primes less than or equal to

*m*. The

*n*-th prime number

*p*

_{n}can then be written as

## 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.

## Prime number fun

- GIMPS
- Prime curious at the prime pages
- The Prime Number Shitting Bear is a web cartoon

## Quotes

*"The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers."*Bill Gates, The Road Ahead, Viking Penguin (1995)

## External Links

- Chris K. Caldwell: "The prime pages", http://www.utm.edu/research/primes/
- Chris K. Caldwell: "Illegal Prime", http://primes.utm.edu/glossary/page.php/Illegal.html
- J. O'Connor and E. F. Robertson: "MacTutor history of prime numbers", http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Prime_numbers.html
- Carlos Rivera: "The prime puzzles" http://www.primepuzzles.net/
- Sebastián Martín Ruiz Home Page: http://personal.telefonica.terra.es/web/smruiz/
- Manindra Agarwal, Nitin Saxena, Neeraj Kayal, "PRIMES is in P", Preprint, August 6, 2002, http://www.cse.iitk.ac.in/news/primality.html
- The "PRIMES is in P" FAQ http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html
- The First 100,000 Prime Numbers, http://www.ibiblio.org/gutenberg/cgi-bin/sdb/t9.cgi/t9.cgi?entry=65
- 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: http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html

## Books

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