Prime numberCategory:Number theory\nIn mathematics, a prime number, or prime for short, is a natural number greater than 1 whose only positive divisors are 1 and itself. 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. The sequence of prime numbers begins
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:
Finding prime numbersThe 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
Open questionsThere are many open questions about prime numbers. For example:\n* Goldbach's conjecture: Can every even integer greater than 2 be written as a sum of two primes?\n* 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?\n* Does the Fibonacci sequence contain an infinite number of primes?\n* Are there infinitely many Fermat primes?\n* Is there always a prime number between n2 and (n + 1)2 for every n?\n* Are there infinitely many primes of the form n2 + 1?The largest known primeThe largest known prime is 224036583 − 1 (this number is 7,235,733 digits long); it is the 41st known Mersenne prime. M24036583 was found on May 15 2004 by a collaborative effort known as GIMPS and it was announced in late May 2004. The next largest known prime is 220996011 − 1 (this number is 6,320,430 digits long); it is the 40th known Mersenne prime. M20996011 was also found on November 17 2003 by a collaborative effort known as GIMPS and announced in early December 2003. The third largest known prime is 213466917 − 1 (this number is 4,053,946 digits long). It is the 39th known Mersenne prime M13466917 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 256k for some positive integer k, and searching for possible primes within the interval [256kn + 1, 256k(n + 1) − 1].\nIn 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.\nSuch numbers, when converted to binary and executed as a computer program, perform acts encumbered by applicable law in one or more jurisdictions.ApplicationsExtremely large prime numbers (that is, greater than 10100) are used in several public key cryptography algorithms. Primes are also used for hash tables and pseudorandom number generators.Primality tests\nMain 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.Some special types of primesA 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:
Prime gapsLet pn denote the n-th prime number (i.e. p1 = 2, p2 = 3, etc.). The gap gn between the consecutive primes pn and pn + 1 is the number of (composite) numbers between them, i.e. gn = pn + 1 − pn − 1. (Slightly different definitions are sometimes used.) We have g1 = 0, g2 = g3 = 1, and g4 = 3. The sequence {gn} 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 gn > N. (Choose n so that pn 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 (gn/pn) approaches zero as n approaches infinity. 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. Note that the Twin Prime Conjecture simply asserts that gn = 1 for infinitely many integers n.Formulas yielding prime numbers\nMain 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) = 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. 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.GeneralizationsThe 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. \nPrime ideals are an important tool and object of study in commutative algebra, algebraic number theory and algebraic geometry.\nThe 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
Prime number fun
Books
External links
|
||
"Hell is a half-filled auditorium." - Robert Frost (1874-1963) |
