Prime number

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 20 prime numbers are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 and 71.

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.

Table of contents 1 Representing natural numbers as products of primes 2 How many prime numbers are there? 3 Finding prime numbers 4 Some properties of primes 5 Open Questions 6 The largest known prime 7 Applications 8 Some special types of primes 9 Prime gaps 10 Formulas yielding prime numbers 11 Generalizations 12 Quotes 12.1 The First 25 Primes 13 External Links

Representing natural numbers as products of primes

An important result 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

23244 = 2² × 3 × 13 × 149.

How many prime numbers are there?

There are infinitely many prime numbers. The oldest known proof for this statement is a reductio ad absurdum dating to the Greek mathematician Euclid. The argument goes as follows:

Assume that there are only a finite number of primes. If you multiply all the primes together, and add one, the resulting number, when divided by any of the primes, has a remainder of one. Therefore it cannot be divided by any of what were supposedly all the primes, and it must be another prime, or divisible by a prime that we have omitted from our list of all the primes. We arrive at a contradiction, so our original assumption (that there is a finite number of primes) must be false. So there are an infinite number of primes.

Other mathematicians have given their own proofs; for example Kummer[?]'s is particularly elegant and Furstenberg provides one using topological terms.

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

A simple but inefficient way to compute a list of all the prime numbers up to a given limit is the algorithm called the "Sieve of Eratosthenes".

In practice though, to check whether a given large number (say, up to a few thousand digits) is prime, one uses primality tests which are probabilistic 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.
• 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ⁿ 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.
• 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 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 = 6n - 1 or 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).

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² and (n + 1)² for every n?
• Are there infinitely many primes of the form n² + 1?

The largest known prime

The largest known prime is 2^13466917-1 (this number is 4,053,946 digits long). It is the 39th Mersenne prime M_13466917 found by a collaborative effort known as GIMPS on November 14, 2001 and announced in early December 2001 after double checking. The next largest known is 2^6972593-1, (this number is 2,098,960 digits long), also a Mersenne prime, found by GIMPS on June 1, 1999. All largest known primes are Mersenne primes, 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¹⁰⁰) make public key cryptography possible. Primes are also used for hash tables and pseudorandom number generators.

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

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 Fermat primes.

The base-ten digit sequence of a prime can be a palindrome, as in the prime 10³¹⁵¹² + 9700079 · 10¹⁵⁷⁵³ + 1. Or 11. Or 2. This is a trivial statement.

Prime gaps

The gap between the n-th prime p_n and the n+1-st prime p_n+1 is defined to be 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 and g₂ = 1. The sequence (g_n) 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 g_n > N. On the other hand, for any positive real number ε, there exists a start index n₀ such that g_n < ε · p_n for all n > n₀.

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² - 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 exists a polynomial in 26 variables with integer coefficients such that, if you plug in integers for the variables, the set of positive values is equal to the set of prime numbers. However, for some values of the variables, the result is negative and can then be composite.

The following function yields all the primes, and only primes, for natural numbers n:

<math>f(n) = 2 + (2n! \ mod \ (n+1))</math>

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.

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

<math>\pi(m) = \sum_{j=2}^m \frac

{ \sin^2 ( {\pi \over j} (j-1)!^2 ) } { \sin^2( {\pi \over j} ) } </math>

or, alternatively,

<math> \pi(m) = \sum_{j=2}^m \left[ {(j-1)! + 1 \over j} - \left[{(j-1)! \over j}\right] \right] </math>

These definitions are equivalent; π(m) is the number of primes less than or equal to m. The n-th prime number p_n can then be written as

<math>p_n = 1 + \sum_{m=1}^{2^n} \left[ \left[ { n \over 1 + \pi(m) } \right]^{1 \over n} \right]</math>

Another approach does not use factorials and Wilson's theorem, but also heavily employs the floor function (S. M. Ruiz 2000): first define

<math>G(k) = k - 1 + \sum_{j=2}^k \left[ {2 \over j} \left(1 + \sum_{s=1}^{\left[\sqrt{j}\right]} \left(\left[{ j-1 \over s}\right] - \left[{j \over s}\right]\right) \right)\right] </math>

and then

<math>p_n = 1 + \sum_{k=1}^{2([n \ln(n)]+1)} \left(1 - \left[{G(k) \over n} \right]\right) </math>

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,...} 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.

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)

The First 25 Primes

n	pn	Binary	1/p	Len
1	2	10	0·5	1
2	3	11	0·3...	1
3	5	101	0·2	1
4	7	111	0·142857...	6
5	11	1011	0·09...	2
6	13	1101	0·076923...	6
7	17	10001	0·0588235294117647...	16
8	19	10011	0·052631578947368421...	18
9	23	10111	0·0434782608695652173913...	22
10	29	11101	0·0344827586206896551724137   931...	28
11	31	11111	0·032258064516129...	15
12	37	100101	0·027...	3
13	41	101001	0·02439...	5
14	43	101011	0·023255813953488372093...	21
15	47	101111	0·0212765957446808510638297   872340425531914893617...	46
16	53	110101	0·0188679245283...	13
17	59	111011	0·0169491525423728813559322   0338983050847457627118644   06779661...	58
18	61	111101	0·0163934426229508196721311   4754098360655737704918032   7868852459...	60
19	67	1000011	0·0149253731343283582089552   23880597...	33
20	71	1000111	0·0140845070422535211267605   6338028169...	35
21	73	1001001	0·01369863...	8
22	79	1001111	0·0126582278481...	13
23	83	1010011	0·0120481927710843373493975   9036144578313253...	41
24	89	1011001	0·0112359550561797752808988   7640449438202247191...	44
25	97	1100001	0·0103092783505154639175257   7319587628865979381443298   9690721649484536082474226   804123711340206185567...	96

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
• J. O'Connor and E. F. Robertson: "MacTutor history of prime numbers", http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Prime_numbers
• 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
• The "PRIMES is in P" FAQ http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ (http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ)
• The First 100,000 Prime Numbers, http://www.ibiblio.org/gutenberg/cgi-bin/sdb/t9.cgi/t9.cgi?entry=65