Copyright © Philip M. Parker, INSEAD. Terms of Use.
Definition: Prime Number |
Prime NumberNoun1. An integer that has no integral factors but itself and 1. Source: WordNet 1.7.1 Copyright © 2001 by Princeton University. All rights reserved. |
| Context | Synonyms within Context (source: adapted from Roget's Thesaurus). |
Number | Sum, difference, complement, subtrahend; product; multiplicand, multiplier, multiplicator; coefficient, multiple; dividend, divisor, factor, quotient, submultiple; fraction, rational number; surd, irrational number; transcendental number; mixed number, complex number, complex conjugate; numerator, denominator; decimal, circulating decimal, repetend; common measure, aliquot part; prime number, prime, relative prime, prime factor, prime pair; reciprocal; totient. |
| Source: adapted from Roget's Thesaurus. | |
(From Wikipedia, the free Encyclopedia)
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
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
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:
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.
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.
There are many open questions about prime numbers. For example:
The next 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].
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.
Extremely 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.
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:
Primes of the form 2n-1 are known as Mersenne primes, while primes of the form 22n+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 1031512 + 9700079 · 1015753 + 1.
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.
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 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:
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
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.
Representing natural numbers as products of primes
See Prime factorization algorithm for details.How many prime numbers are there?
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 topological terms.Finding prime numbers
Some properties of primes
Open Questions
The largest known prime
The largest known prime is 220996011-1 (this number is 6,320,430 digits long). It is the 40th known Mersenne prime M20996011 found by a collaborative effort known as GIMPS and announced in early December 2003. Applications
Some special types of primes
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.Prime gaps
Formulas yielding prime numbers
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))
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 thenGeneralizations
Prime number fun
Quotes
External Links
Books
Source: adapted by the editor from Wikipedia, the free encyclopedia under a copyleft GNU Free Documentation License (GFDL) from the article "Prime number."
Crosswords: Prime Number |
| English words defined with "prime number": Prime factor. (references) |
| Specialty definitions using "prime number": prime number theorem. (references) |
| Domain | Usage | |
Screenplays | I have it at 42 exposures, but I wanna get it to 47 becauseit's a prime number. (Alias; writing credit: Robert Soulé; Henri de Turenne) | |
Source: compiled by the editor from various references; see credits. | ||
| Domain | Title |
Books | |
Periodicals |
|
Source: compiled by the editor from various references; see credits. | |
Expression using "prime number": prime number theorem. Additional references. | |
| Source: compiled by the editor from various references; see credits. |
| The following statistics estimate the number of searches per day across the major English-language search engines as identified by various trade publications. Hyperlinks lead to commercial use of the expression at Amazon.com. |
| Expression | Frequency per Day |
prime number | 488 |
the prime number theorem | 7 |
| Source: compiled by the editor from various references; see credits. | |
| Language | Translations for "prime number"; alternative meanings/domain in parentheses. | ||||||||||||||||||||||||||||||||||
Czech | prvoèíslo. (various references) | ||||||||||||||||||||||||||||||||||
Danish | primtal. (various references) | ||||||||||||||||||||||||||||||||||
Dutch | priemgetal (prime), ondeelbaar getal. (various references) | ||||||||||||||||||||||||||||||||||
Finnish | alkuluku. (various references) | ||||||||||||||||||||||||||||||||||
French | nombre premier (prime). (various references) | ||||||||||||||||||||||||||||||||||
German | Primzahl (indivisible number, prime). (various references) | ||||||||||||||||||||||||||||||||||
Greek | πρώτος αριθμός, περιττόσ αριθμόσ (uneven). (various references) | ||||||||||||||||||||||||||||||||||
Hungarian | törzsszám (prime). (various references) | ||||||||||||||||||||||||||||||||||
Italian | numero primo. (various references) | ||||||||||||||||||||||||||||||||||
Manx | earroo ard, ard-earroo (cock-up). (various references) | ||||||||||||||||||||||||||||||||||
Pig Latin | imepray umbernay número primo. (various references) простое число (prime). (various references) número primo. (various references) primtal (prime). (various references) asal sayı (prime). (various references) | ||||||||||||||||||||||||||||||||||
Scrabble® Enable2K-Verified Anagrams | |
| Words within the letters "b-e-e-i-m-m-n-p-r-r-u" | |
-2 letters: prenumber. | |
-3 letters: numberer, perineum, renumber. | |
-4 letters: brimmer, bumpier, eremuri, murrine, premier, premium, premune, primmer, repiner, ripener, rummier, unriper. | |
-5 letters: bemire, berime, bireme, briner, bummer, bumper, burier, burner, burnie, embrue, empire, epimer, erbium, ermine, imbrue, immune, immure, impure, member, mermen, mumper, murein, murine, number, premen, premie, primer, pruner, punier, purine, repine, rimmer, rubier, ruiner, rummer. | |
| Source: compiled by the editor from various references; see credits. SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the U.S.A and Canada by Hasbro Inc., and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc. Mattel and Spear are not affiliated with Hasbro. | |
| 1. Definition 2. Crosswords 3. Usage: Modern 4. Usage: Commercial | 5. Expressions 6. Expressions: Internet 7. Translations: Modern 8. Anagrams | 9. Bibliography |
Copyright © Philip M. Parker, INSEAD. Terms of Use.
