Prime number

The Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. In Mathematics, the Sieve of Eratosthenes is a simple ancient Algorithm for finding all Prime numbers up to a specified integer In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation It is the predecessor to the modern Sieve of Atkin, which is faster but more complex. In Mathematics, the sieve of Atkin is a fast modern Algorithm for finding all Prime numbers up to a specified integer The eponymous Sieve of Eratosthenes was created in the 3rd century BC by Eratosthenes, an ancient Greek mathematician. The 3rd century BC started the first day of 300 BC and ended the last day of 201 BC Eratosthenes of Cyrene ( Greek; 276 BC - 194 BC was a Greek Mathematician, Poet, athlete, Geographer and The term ancient Greece refers to the period of Greek history lasting from the Greek Dark Ages ca A mathematician is a person whose primary area of study and research is the field of Mathematics.

There are hints in the surviving records of the ancient Egyptians that they had some knowledge of prime numbers: the Egyptian fraction expansions in the Rhind papyrus, for instance, have quite different forms for primes and for composites. Ancient Egypt was an Ancient Civilization in eastern North Africa, concentrated along the lower reaches of the Nile River in what is now An Egyptian fraction is the sum of distinct Unit fractions such as \tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{16} The Rhind Mathematical Papyrus (RMP (also designated as papyrus British Museum 10057 and pBM 10058 is named after Alexander Henry Rhind, a Scottish However, the earliest surviving records of the explicit study of prime numbers come from the Ancient Greeks. The term ancient Greece refers to the period of Greek history lasting from the Greek Dark Ages ca Euclid's Elements (circa 300 BC) contain important theorems about primes, including the infinitude of primes and the fundamental theorem of arithmetic. Euclid's Elements ( Greek:) is a mathematical and geometric Treatise consisting of 13 books written by the Greek Events By place Egypt Pyrrhus, the King of Epirus, is taken as a hostage to Egypt after the Battle of Ipsus In Number theory, the fundamental theorem of arithmetic (or unique-prime-factorization theorem) states that every Natural number greater than 1 can be written Euclid also showed how to construct a perfect number from a Mersenne prime. In mathematics a perfect number is defined as a positive integer which is the sum of its proper positive Divisors that is the sum of the positive divisors excluding In Mathematics, a Mersenne number is a positive integer that is one less than a Power of two: M_n=2^n-1 The Sieve of Eratosthenes, attributed to Eratosthenes, is a simple method to compute primes, although the large primes found today with computers are not generated this way. In Mathematics, the Sieve of Eratosthenes is a simple ancient Algorithm for finding all Prime numbers up to a specified integer Eratosthenes of Cyrene ( Greek; 276 BC - 194 BC was a Greek Mathematician, Poet, athlete, Geographer and

After the Greeks, little happened with the study of prime numbers until the 17th century. In 1640 Pierre de Fermat stated (without proof) Fermat's little theorem (later proved by Leibniz and Euler). Pierre de Fermat pjɛːʁ dəfɛʁ'ma ( 17 August 1601 or 1607/8 &ndash 12 January 1665) was a French Lawyer at the Fermat's little theorem (not to be confused with Fermat's last theorem) states that if p is a Prime number, then for any Integer a A special case of Fermat's theorem may have been known much earlier by the Chinese. Fermat conjectured that all numbers of the form 2^2ⁿ + 1 are prime (they are called Fermat numbers) and he verified this up to n = 4. In Mathematics, a Fermat number, named after Pierre de Fermat who first studied them is a positive integer of the form F_{n} = 2^{2^{ However, the very next Fermat number 2³²+1 is composite (one of its prime factors is 641), as Euler discovered later, and in fact no further Fermat numbers are known to be prime. The French monk Marin Mersenne looked at primes of the form 2^p - 1, with p a prime. Marin Mersenne, Marin Mersennus or le Père Mersenne ( September 8, 1588 &ndash September 1, 1648) was They are called Mersenne primes in his honor. In Mathematics, a Mersenne number is a positive integer that is one less than a Power of two: M_n=2^n-1

Euler's work in number theory included many results about primes. He showed the infinite series ¹/₂ + ¹/₃ + ¹/₅ + ¹/₇ + ¹/₁₁ + … is divergent. In the third century BC Euclid proved the existence of infinitely many Prime numbers In the 18th century Leonhard Euler proved a stronger statement the sum In Mathematics, a series is often represented as the sum of a Sequence of terms That is a series is represented as a list of numbers with In 1747 he showed that the even perfect numbers are precisely the integers of the form 2^p-1(2^p-1) where the second factor is a Mersenne prime. It is believed no odd perfect numbers exist, but there is still no proof.

At the start of the 19th century, Legendre and Gauss independently conjectured that as x tends to infinity, the number of primes up to x is asymptotic to x/log(x), where log(x) is the natural logarithm of x. Ideas of Riemann in his 1859 paper on the zeta-function sketched a program which would lead to a proof of the prime number theorem. This outline was completed by Hadamard and de la Vallée Poussin, who independently proved the prime number theorem in 1896. Jacques Salomon Hadamard ( December 8, 1865 – October 17, 1963) was a French Mathematician best known for his proof of Charles-Jean Étienne Gustave Nicolas Baron de la Vallée Poussin ( August 14[[ 866]] - March 2[[ 962]] was a Belgian Mathematician.

Proving a number is prime is not done (for large numbers) by trial division. Many mathematicians have worked on primality tests for large numbers, often restricted to specific number forms. A primality test is an Algorithm for determining whether an input number is prime. This includes Pépin's test for Fermat numbers (1877), Proth's theorem (around 1878), the Lucas–Lehmer test for Mersenne numbers (originated 1856),^[1] and the generalized Lucas–Lehmer test. In Mathematics, Pépin's test is a Primality test, which can be used to determine whether a Fermat number is prime. In Mathematics, Proth's theorem in Number theory is a Primality test for Proth numbers It states that if p is a Proth number This article is about the Lucas–Lehmer test (LLT that only applies to Mersenne numbers This article is about the generalized Lucas–Lehmer test for primality More recent algorithms like APRT-CL, ECPP and AKS work on arbitrary numbers but remain much slower. The Adleman–Pomerance–Rumely primality test ( APR) is a Deterministic algorithm that tests if a positive integer is prime. Elliptic Curve Primality Proving (ECPP is a method based on Elliptic curves to prove the primality of a number The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving

For a long time, prime numbers were thought as having no possible application outside of pure mathematics; this changed in the 1970s when the concepts of public-key cryptography were invented, in which prime numbers formed the basis of the first algorithms such as the RSA cryptosystem algorithm. Broadly speaking pure mathematics is Mathematics motivated entirely for reasons other than application Public-key cryptography, also known as asymmetric cryptography, is a form of Cryptography in which the key used to encrypt a message differs from the key In Cryptography, RSA is an Algorithm for Public-key cryptography.

Since 1951 all the largest known primes have been found by computers. A computer is a Machine that manipulates data according to a list of instructions. The search for ever larger primes has generated interest outside mathematical circles. The Great Internet Mersenne Prime Search and other distributed computing projects to find large primes have become popular in the last ten to fifteen years, while mathematicians continue to struggle with the theory of primes. The Great Internet Mersenne Prime Search ( GIMPS) is a collaborative project of volunteers who use Prime95 and MPrime Computer software that can Distributed computing deals with Hardware and Software Systems containing more than one processing element or Storage element concurrent

Primality of one

Until the 19th century, most mathematicians considered the number 1 a prime, and there is still a large body of mathematical work that is valid despite labeling 1 a prime, such as the work of Stern and Zeisel. Moritz Abraham Stern ( June 29, 1807 &ndash January 30, 1894) was a German mathematician Derrick Norman Lehmer's list of primes up to 10006721, reprinted as late as 1956,^[2] started with 1 as its first prime. Derrick Norman Lehmer ( 27 July 1867, Somerset Indiana, USA &mdash 8 September 1938 in Berkeley California, USA ^[3] Henri Lebesgue is said to be the last professional mathematician to call 1 prime. Henri Léon Lebesgue leɔ̃ ləˈbɛg ( June 28, 1875, Beauvais &ndash July 26, 1941, Paris) was a French The change in label occurred so that the fundamental theorem of arithmetic, as stated, is valid, i. In Number theory, the fundamental theorem of arithmetic (or unique-prime-factorization theorem) states that every Natural number greater than 1 can be written e. , “each number has a unique factorization into primes”^[4]^[5]^[6]

Prime divisors

Illustration showing that 11 is a prime number while 12 is not.

The fundamental theorem of arithmetic states that every positive integer larger than 1 can be written as a product of one or more primes in a way which is unique except possibly for the order of the prime factors. In Number theory, the fundamental theorem of arithmetic (or unique-prime-factorization theorem) states that every Natural number greater than 1 can be written In Mathematics and Logic, the phrase "there is one and only one " is used to indicate that exactly one object with a certain property exists In Mathematics, a divisor of an Integer n, also called a factor of n, is an integer which evenly divides n without The same prime factor may occur multiple times. Primes can thus be considered the “basic building blocks” of the natural numbers. For example, we can write

$23244 = 2^2 \times 3 \times 13 \times 149$

and any other factorization of 23244 as the product of primes will be identical except for the order of the factors. There are many prime factorization algorithms 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.

Properties of primes

When written in base 10, all prime numbers except 2 and 5 end in 1, 3, 7 or 9. The decimal ( base ten or occasionally denary) Numeral system has ten as its base. (Numbers ending in 0, 2, 4, 6 or 8 represent multiples of 2 and numbers ending in 0 or 5 represent multiples of 5. )

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. Euclid's lemma ( Greek) is a generalization of Proposition 30 of Book VII of Euclid's Elements. 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. In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers In Abstract algebra, a field is an Algebraic structure in which the operations of Addition, Subtraction, Multiplication and division ↔ Put another way: n is prime if and only if φ(n) = n − 1. In Number theory, the totient \varphi(n of a Positive integer n is defined to be the number of positive integers less than or equal to

If p is prime and a is any integer, then a^p − a is divisible by p (Fermat's little theorem). Fermat's little theorem (not to be confused with Fermat's last theorem) states that if p is a Prime number, then for any Integer a

If p is a prime number other than 2 and 5, ¹/_p is always a recurring decimal, whose period is p − 1 or a divisor of p − 1. A Decimal representation of a Real number is called a repeating decimal (or recurring decimal) if at some point it becomes periodic: there is This can be deduced directly from Fermat's little theorem. Fermat's little theorem (not to be confused with Fermat's last theorem) states that if p is a Prime number, then for any Integer a ¹/_p expressed likewise in base q (other than base 10) has similar effect, provided that p is not a prime factor of q. The article on recurring decimals shows some of the interesting properties. A Decimal representation of a Real number is called a repeating decimal (or recurring decimal) if at some point it becomes periodic: there is

An integer p > 1 is prime if and only if the factorial (p − 1)! + 1 is divisible by p (Wilson's theorem). Definition The factorial function is formally defined by n!=\prod_{k=1}^n k In Mathematics, Wilson's theorem states that p > 1 is a Prime number If and only if (p-1!\ \equiv\ -1\ (\mbox{mod}\ p Conversely, an integer n > 4 is composite if and only if (n − 1)! is divisible by n.

If n is a positive integer greater than 1, then there is always a prime number p with n < p < 2n (Bertrand's postulate). Bertrand's postulate (actually a Theorem) states that if n > 3 is an Integer, then there always exists at least one Prime number p

Adding the reciprocals of all primes together results in a divergent infinite series (proof). In Mathematics, a series is often represented as the sum of a Sequence of terms That is a series is represented as a list of numbers with In the third century BC Euclid proved the existence of infinitely many Prime numbers In the 18th century Leonhard Euler proved a stronger statement the sum 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 + O(1) for x → ∞. In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments

In every arithmetic progression a, a + q, a + 2q, a + 3q,… where the positive integers a and q are coprime, there are infinitely many primes (Dirichlet's theorem on arithmetic progressions). In Mathematics, the Integers a and b are said to be coprime or relatively prime if they have no common factor other than In Number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem states that for any two positive Coprime Integers a and

The characteristic of every field is either zero or a prime number. In Mathematics, the characteristic of a ring R, often denoted char( R) is defined to be the smallest number of times one must add the ring's

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ⁿ. In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Number theory, for a given Prime number p, the p -adic order or additive p -adic valuation of a number n is (Sylow theorems. In Mathematics, specifically Group theory, the Sylow theorems, named after Ludwig Sylow, form a partial converse to Lagrange's theorem, which )

If G is a finite group and p is a prime number dividing the order of G, then G contains an element of order p. (Cauchy Theorem)

The prime number theorem says that the proportion of primes less than x is asymptotic to ¹/_{ln x} (in other words, as x gets very large, the likelihood that a number less than x is prime is inversely proportional to the number of digits in x). Cauchy's theorem is a theorem in the mathematics of Group theory, named after Augustin Louis Cauchy.

The Copeland-Erdős constant 0. The Copeland-Erdős constant is the concatenation of "0" with the base 10 representations of the Prime numbers in order 235711131719232931374143…, obtained by concatenating the prime numbers in base ten, is known to be an irrational number. The decimal ( base ten or occasionally denary) Numeral system has ten as its base. In Mathematics, an irrational number is any Real number that is not a Rational number — that is it is a number which cannot be expressed as a fraction

The value of the Riemann zeta function at each point in the complex plane is given as a meromorphic continuation of a function, defined by a product over the set of all primes for Re(s) > 1:

$\zeta(s)= \sum_{n=1}^\infin \frac{1}{n^s} = \prod_{p} \frac{1}{1-p^{-s}}.$

Evaluating this identity at different integers provides an infinite number of products over the primes whose values can be calculated, the first two being

$\prod_{p} \frac{1}{1-p^{-1}} = \infty$

$\prod_{p} \frac{1}{1-p^{-2}}= \frac{\pi^2}{6}.$

If p > 1, the polynomial $x^{p-1}+x^{p-2}+ \cdots + 1$ is irreducible over Z/pZ if and only if p is prime. In Mathematics, the Riemann zeta function, named after German mathematician Bernhard Riemann, is a function of great significance in

An integer n is prime if and only if the $n t h$ Chebyshev polynomial of the first kind $T n (x)$ , divided by $x$ is irreducible in $Z [x]$ . Also $T_{n}(x) \equiv x^n$ if and only if $n$ is prime.

All prime numbers above 3 are of form 6n − 1 or 6n + 1, because all other numbers are divisible by 2 or 3. Generalizing this, all prime numbers above q are of form q#·n + m, where 0 < m < q, and m has no prime factor ≤ q. The primorial has two similar but distinct meanings The name is attributed to Harvey Dubner and is a Portmanteau of prime and Factorial

Classification of prime numbers

Two ways of classifying prime numbers, class n+ and class n−, were studied by Paul Erdős and John Selfridge. Paul Erdős ( Hungarian: Erdős Pál, in English occasionally Paul Erdos or Paul Erdös, March 26, 1913 &ndash John L Selfridge is an American Mathematician who has contributed to the field of Analytic number theory.

Determining the class n+ of a prime number p involves looking at the largest prime factor of p + 1. If that largest prime factor is 2 or 3, then p is class 1+. But if that largest prime factor is another prime q, then the class n+ of p is one more than the class n+ of q. Sequences A005105 through A005108 list class 1+ through class 4+ primes.

The class n− is almost the same as class n+, except that the factorization of p − 1 is looked at instead.

The number of prime numbers

There are infinitely many prime numbers

The oldest known proof for the statement that there are infinitely many prime numbers is given by the Greek mathematician Euclid in his Elements (Book IX, Proposition 20). Infinity (symbolically represented with ∞) comes from the Latin infinitas or "unboundedness Euclid states the result as "there are more than any given [finite] number of primes", and his proof is essentially the following:

Consider any finite set of primes. Multiply all of them together and add one (see Euclid number). In Mathematics, Euclid numbers are Integers of the form E n = p n # + 1 where p The resulting number is not divisible by any of the primes in the finite set we considered, because dividing by any of these would give a remainder of one. Because all non-prime numbers can be decomposed into a product of underlying primes, then either this resultant number is prime itself, or there is a prime number or prime numbers which the resultant number could be decomposed into but are not in the original finite set of primes. Either way, there is at least one more prime that was not in the finite set we started with. This argument applies no matter what finite set we began with. So there are more primes than any given finite number.

This previous argument explains why the product P of finitely many primes plus 1 must be divisible by some prime not among those finitely many primes (possibly itself).

The proof is sometimes phrased in a way that leads the student to conclude that P + 1 must itself be prime, and think that Euclid's proof says the prime product plus 1 is always prime. The simple example of (2 · 3 · 5 · 7 · 11 · 13) + 1 = 30,031 = 59 · 509 (both primes) shows that this is not the case. In fact, any set of primes which does not include 2 will have an odd product. Adding 1 to this product will always produce an even number, which will be divisible by 2 (and therefore not be prime). See also Euclid's theorem. Euclid's theorem is a fundamental statement in Number theory which asserts that there are infinitely many Prime numbers There are several well-known proofs

Other mathematicians have given other proofs. One of these (due to Euler) shows that the sum of the reciprocals of all prime numbers diverges. In the third century BC Euclid proved the existence of infinitely many Prime numbers In the 18th century Leonhard Euler proved a stronger statement the sum Another proof based on Fermat numbers was given by Goldbach. In Mathematics, a Fermat number, named after Pierre de Fermat who first studied them is a positive integer of the form F_{n} = 2^{2^{ In Mathematics, a Fermat number, named after Pierre de Fermat who first studied them is a positive integer of the form F_{n} = 2^{2^{ Christian Goldbach ( March 18, 1690 &ndash November 20, 1764) was a Prussian Mathematician who also studied Law ^[7] Kummer's is particularly elegant^[8] and Harry Furstenberg provides one using general topology. Ernst Eduard Kummer ( 29 January 1810 - 14 May 1893) was a German Mathematician. Hillel (Harry Furstenberg (הלל (הארי פורסטנברג is an Israeli Mathematician, a member of the Israel Academy of Sciences and Humanities and U In Number theory, Hillel Furstenberg 's proof of the infinitude of primes is a celebrated topological proof that the Integers contain ^[9]^[10]

Counting the number of prime numbers below a given number

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

The prime-counting function π(x) is defined as the number of primes up to x. In Mathematics, the prime-counting function is the function counting the number of Prime numbers less than or equal to some Real number x There are known algorithms to compute exact values of π(x) faster than it would be possible to compute each prime up to x. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation Values as large as π(10²⁰) can be calculated quickly and accurately with modern computers. Thus, e. g. , π(100000) = 9592, and π(10²⁰) = 2,220,819,602,560,918,840.

For larger values of x, beyond the reach of modern equipment, the prime number theorem provides a good estimate: π(x) is approximately x/ln(x). Even better estimates are known.

Location of prime numbers

Finding prime numbers

The ancient Sieve of Eratosthenes is a simple way to compute all prime numbers up to a given limit, by making a list of all integers and repeatedly striking out multiples of already found primes. In Mathematics, the Sieve of Eratosthenes is a simple ancient Algorithm for finding all Prime numbers up to a specified integer The modern Sieve of Atkin is more complicated, but faster when properly optimized. In Mathematics, the sieve of Atkin is a fast modern Algorithm for finding all Prime numbers up to a specified integer

In practice one often wants to check whether 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. Probability is the likelihood or chance that something is the case or will happen It is possible to quickly check whether a given large number (say, up to a few thousand digits) is prime using probabilistic primality tests. A primality test is an Algorithm for determining whether an input number is prime. 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". Some of these tests are not perfect: there may be some composite numbers, called pseudoprimes for the respective test, that will be declared "probably prime" no matter what witness is chosen. A pseudoprime is a Probable prime (an Integer which shares a property common to all Prime numbers which is not actually prime However, the most popular probabilistic tests do not suffer from this drawback.

One method for determining whether a number is prime is to divide by all primes less than or equal to the square root of that number. If any of the divisions come out as an integer, then the original number is not a prime. Otherwise, it is a prime. One need not actually calculate the square root; once one sees that the quotient is less than the divisor, one can stop. In Mathematics, a quotient is the result of a division. For example when dividing 6 by 3 the quotient is 2 while 6 is called the dividend, and 3 the This is known as trial division; it is the simplest primality test and it quickly becomes impractical for testing large integers because the number of possible factors grows exponentially as the number of digits in the number-to-be-tested increases.

Primality tests

Main article: primality test

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

A probable prime is an integer which, by virtue of having passed a certain test, is considered to be probably prime. The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving The Fermat primality test is a probabilistic test to determine if a number is probably prime. This article is about the generalized Lucas–Lehmer test for primality Elliptic Curve Primality Proving (ECPP is a method based on Elliptic curves to prove the primality of a number In Number theory, a probable prime (PRP is an Integer that satisfies a specific condition also satisfied by all Prime numbers. Probable primes which are in fact composite (such as Carmichael numbers) are called pseudoprimes. In Number theory, a Carmichael number is a composite positive Integer n which satisfies the Congruence b^{n-1}~\equiv 1 \pmod{n} A pseudoprime is a Probable prime (an Integer which shares a property common to all Prime numbers which is not actually prime

In 2002, Indian scientists at IIT Kanpur discovered a new deterministic algorithm known as the AKS algorithm. The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving The amount of time that this algorithm takes to check whether a number N is prime depends on a polynomial function of the number of digits of N (i. In Computational complexity theory, P, also known as PTIME or DTIME ( n O(1 is one of the most fundamental Complexity e. of the logarithm of N).

Formulas yielding prime numbers

Main article: formula for primes

There is no known formula for primes which is more efficient at finding primes than the methods mentioned above under “Finding prime numbers”. In Mathematics, a formula for primes is a formula generating the Prime numbers exactly and without exception In Mathematics, a formula for primes is a formula generating the Prime numbers exactly and without exception

There is a set of Diophantine equations in 9 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. In Mathematics, a Diophantine equation is an indeterminate Polynomial Equation that allows the variables to be Integers only This can be used to obtain a single formula with the property that all its positive values are prime.

There is no polynomial, even in several variables, that takes only prime values. In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations For example, the curious polynomial in one variable f(n) = n² − n + 41 yields primes for n = 0,…, 40,43 but f(41) and f(42) are composite. However, there are polynomials in several variables, whose positive values as the variables take all positive integer values are exactly the primes.

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 formulas which also produce primes.

Special types of primes from formulas for 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. In Mathematics, primorial primes are Prime numbers of the form pn # ± 1 where pn # is the The primorial has two similar but distinct meanings The name is attributed to Harvey Dubner and is a Portmanteau of prime and Factorial A prime is called factorial if it is of the form n! ± 1. A factorial prime is a Prime number that is one less or one more than a Factorial (all factorials above 1 are even Definition The factorial function is formally defined by n!=\prod_{k=1}^n k The first factorial primes are:

n! − 1 is prime for n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, … (sequence A002982 in OEIS)

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

The largest known primorial prime is Π(392113) + 1, found by Heuer in 2001. The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences ^[11] The largest known factorial prime is 34790! − 1, found by Marchal, Carmody and Kuosa in 2002. ^[12] It is not known whether there are infinitely many primorial or factorial primes.

Primes of the form 2^p − 1, where p is a prime number, are known as Mersenne primes, while primes of the form $2^{2^n} + 1$ are known as Fermat primes. In Mathematics, a Mersenne number is a positive integer that is one less than a Power of two: M_n=2^n-1 In Mathematics, a Fermat number, named after Pierre de Fermat who first studied them is a positive integer of the form F_{n} = 2^{2^{ Prime numbers p where 2p + 1 is also prime are known as Sophie Germain primes. In Number theory, a Prime number p is a Sophie Germain prime if 2 p + 1 is also prime The following list is of other special types of prime numbers that come from formulas:

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. In Number theory, a Wieferich prime is a Prime number p such that p 2 divides 2 p &minus 1 &minus 1 A Wilson prime is a Prime number p such that p ² divides ( p &minus 1! + 1 where "!" denotes the Factorial function; compare In Number theory, a Wall-Sun-Sun prime is a certain kind of Prime number which is conjectured to exist although none are known In Mathematics, a unique prime is a certain kind of Prime number. This can be abbreviated to NSW which is also the abbreviation of the state of New South Wales in Australia. In Mathematics, a Smarandache-Wellin number is an Integer that in a given base is the Concatenation of the first n Prime numbers written A Wagstaff prime is a Prime number p of the form p= where q is another prime If E is an Elliptic curve defined over the Rational numbers then a prime p is supersingular for E if the reduction

Some primes are classified according to the properties of their digits in decimal or other bases. For example, numbers whose digits form a palindromic sequence are called palindromic primes, and a prime number is called a truncatable prime if successively removing the first digit at the left or the right yields only new prime numbers. A palindrome is a word phrase number or other sequence of units that can be read the same way in either direction (the adjustment of punctuation and spaces between words A palindromic prime (sometimes called a palprime) is a Prime number that is also a Palindromic number. In Number theory, a left-truncatable prime is a Prime number which in a given base, contains no 0 and if the leading ("left" digit is successively

For a list of special classes of prime numbers‎ see List of prime numbers‎

The distribution of the prime numbers

Further information: Prime number theorem

The distribution of all the prime numbers in the range of 1 to 76,800, from left to right and top to bottom, where each pixel represents a number. Black pixels mean that number is prime and white means it is not prime.

The distribution of all the prime numbers in the range of 1 to 76,800, from left to right and top to bottom, where each pixel represents a number. There are infinitely many Prime numbers Prime numbers may be generated with various Formulas for primes. Black pixels mean that number is prime and white means it is not prime.

The problem of modelling the distribution of prime numbers is a popular subject of investigation for number theorists. The prime numbers are distributed among the natural numbers in a (so far) unpredictable way, but there do appear to be laws governing their behavior. In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an Leonhard Euler commented

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 mind will never penetrate. (Havil 2003, p. 163)

In a 1975 lecture, Don Zagier commented

There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. Don Bernhard Zagier (born 1951) is an American Mathematician whose main area of work is Number theory. The first is that, despite their simple definition and role as the building blocks of the natural numbers, the prime numbers grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision.

(Havil 2003, p. 171)

Additional image with 2310 columns is linked here, preserving multiples of 2,3,5,7,11 in respective columns.

Gaps between primes

Main article: Prime gap

Let p_n denote the nth prime number (i. A prime gap is the difference between two successive Prime numbers The n -th prime gap denoted g n, is the difference between the ( e. p₁ = 2, p₂ = 3, etc. ). The gap g_n between the consecutive primes p_n and p_{n + 1} is the difference between them, i. e.

g_n = p_{n + 1} − p_n.

We have g₁ = 3 − 2 = 1, g₂ = 5 − 3 = 2, g₃ = 7 − 5 = 2, g₄ = 11 − 7 = 4, and so on. The sequence (g_n) of prime gaps has been extensively studied.

For any natural number N larger than 1, the sequence (for the notation N! read factorial)

N! + 2, N! + 3, …, N! + N

is a sequence of N − 1 consecutive composite integers. Definition The factorial function is formally defined by n!=\prod_{k=1}^n k 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! + 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. In Mathematics, the concept of a " limit " is used to describe the Behavior of a function as its argument either "gets close" Note also that the twin prime conjecture asserts that g_n = 2 for infinitely many integers n. The twin prime conjecture is a famous unsolved problem in Number theory that involves Prime numbers It states There are infinitely many primes

Location of the largest known prime

Main articles: Largest known prime and Mersenne prime

The largest known prime, as of August 2007, is 2^32,582,657 − 1 (this number is 9,808,358 digits long); it is the 44th known Mersenne prime. In Mathematics, a Mersenne number is a positive integer that is one less than a Power of two: M_n=2^n-1 A number is an Abstract object, tokens of which are Symbols used in Counting and measuring. In Mathematics, a Mersenne number is a positive integer that is one less than a Power of two: M_n=2^n-1 M_32582657 was found on September 4, 2006 by Curtis Cooper and Steven Boone, professors at the University of Central Missouri (formerly Central Missouri State University) and members of a collaborative effort known as GIMPS. Events 476 - Romulus Augustus, last emperor of the Western Roman Empire, is deposed when Odoacer proclaims himself Year 2006 ( MMVI) was a Common year starting on Sunday of the Gregorian calendar. The meaning of the word professor ( Latin: professor, person who professes to be an expert in some art or science teacher of highest rank) varies The University of Central Missouri (formerly Central Missouri State University) is a four-year public institution in Warrensburg Missouri. The Great Internet Mersenne Prime Search ( GIMPS) is a collaborative project of volunteers who use Prime95 and MPrime Computer software that can Before finding the prime, Cooper and Boone ran the GIMPS software on a peak of 700 university computers for 9 years.

The next two largest known primes are also Mersenne Primes: M_30,402,457 = 2^30,402,457 − 1 (43rd known Mersenne prime, 9,152,052 digits long) and M_25,964,951 = 2^25,964,951 − 1 (42nd known Mersenne prime, 7,816,230 digits long). 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 for Mersenne numbers. This article is about the Lucas–Lehmer test (LLT that only applies to Mersenne numbers

The largest known prime that is not a Mersenne prime is 19,249 × 2^13,018,586 + 1 (3,918,990 digits), a Proth number. In Mathematics, Proth's theorem in Number theory is a Primality test for Proth numbers It states that if p is a Proth number This is also the seventh largest known prime of any form. It was found on March 26, 2007 by the Seventeen or Bust project and it brings them one step closer to solving the Sierpinski problem. Events 1026 - Pope John XIX crowns Conrad II as Holy Roman Emperor. Year 2007 ( MMVII) was a Common year starting on Monday of the Gregorian calendar in the 21st century. Seventeen or Bust is a Distributed computing project started in March 2002 to solve the last seventeen cases in the Sierpinski problem. In Number theory, a Sierpinski number is an odd Natural number k such that integers of the form k 2 n + 1 are composite

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

Awards for finding primes

The Electronic Frontier Foundation (EFF) has offered a US$100,000 prize to the first discoverers of a prime with at least 10 million digits. The Electronic Frontier Foundation ( EFF) is an international non-profit advocacy and legal organization based in the United States with the stated purpose of being dedicated They also offer $150,000 for 100 million digits, and $250,000 for 1 billion digits. In 2000 they paid out $50,000 for 1 million digits.

The RSA Factoring Challenge offered prizes up to US$200,000 for finding the prime factors of certain semiprimes of up to 2048 bits. The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18 1991 to encourage research into Computational number theory In Mathematics, a semiprime (also called biprime or 2- Almost prime, or pq number) is a Natural number that is the product However, the challenge was closed in 2007 after much smaller prizes for smaller semiprimes had been paid out. ^[13]

Generalizations of the prime concept

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

Prime elements in rings

One can define prime elements and irreducible elements in any integral domain. In Abstract algebra, a branch of Mathematics, an integral domain is a Commutative ring with an additive identity 0 and a multiplicative identity 1 such In Mathematics, the adjective irreducible means that an object cannot be expressed as a product of at least two non-trivial factors in a given set In Abstract algebra, a branch of Mathematics, an integral domain is a Commutative ring with an additive identity 0 and a multiplicative identity 1 such For any unique factorization domain, such as the ring Z of integers, the set of prime elements equals the set of irreducible elements, which for Z is {…, −11, −7, −5, −3, −2, 2, 3, 5, 7, 11, …}. In Mathematics, a unique factorization domain (UFD is roughly speaking a Commutative ring in which every element with special exceptions can be uniquely written

As an example, we consider the Gaussian integers Z[i], that is, complex numbers of the form a + bi with a and b in Z. A Gaussian integer is a Complex number whose real and imaginary part are both Integers The Gaussian integers with ordinary addition and multiplication of complex This is an integral domain, and its prime elements are the Gaussian primes. A Gaussian integer is a Complex number whose real and imaginary part are both Integers The Gaussian integers with ordinary addition and multiplication of complex 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 in the Gaussian integers. In general, rational primes (i. e. prime elements in the ring Z of integers) of the form 4k + 3 are Gaussian primes, whereas rational primes of the form 4k + 1 are not.

Prime ideals

In ring theory, one generally replaces the notion of number with that of ideal. In Mathematics, ring theory is the study of rings, Algebraic structures in which addition and multiplication are defined and have similar properties to those In Ring theory, a branch of Abstract algebra, an ideal is a special Subset of a ring. Prime ideals are an important tool and object of study in commutative algebra, algebraic number theory and algebraic geometry. In Mathematics, a prime ideal is a Subset of a ring which shares many important properties of a Prime number in the Ring of integers Commutative algebra is the branch of Abstract algebra that studies Commutative rings their ideals, and modules over such rings Number theory is the branch of Pure mathematics concerned with the properties of Numbers in general and Integers in particular as well as the wider classes Algebraic geometry is a branch of Mathematics which as the name suggests combines techniques of Abstract algebra, especially Commutative algebra, with The prime ideals of the ring of integers are the ideals (0), (2), (3), (5), (7), (11), …

A central problem in algebraic number theory is how a prime ideal factors when it is lifted to an extension field. For example, in the Gaussian integer example above, (2) ramifies into a prime power (1 + i and 1 − i generate the same prime ideal), prime ideals of the form (4k + 3) are inert (remain prime), and prime ideals of the form (4k + 1) split (are the product of 2 distinct prime ideals).

Primes in valuation theory

In class field theory yet another generalization is used. In Mathematics, class field theory is a major branch of Algebraic number theory. Given an arbitrary field K, one considers valuations on K, certain functions from K to the real numbers R. In Abstract algebra, a field is an Algebraic structure in which the operations of Addition, Subtraction, Multiplication and division Every such valuation yields a topology on K, and two valuations are called equivalent if they yield the same topology. In Mathematics, a topological ring is a ring R which is also a Topological space such that both the addition and the multiplication are A prime of K (sometimes called a place of K) is an equivalence class of valuations. In Mathematics, given a set X and an Equivalence relation ~ on X, the equivalence class of an element a in X 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. In Mathematics, a rational number is a number which can be expressed as a Ratio of two Integers Non-integer rational numbers (commonly called fractions In Mathematics, the absolute value (or modulus) of a Real number is its numerical value without regard to its sign. In Mathematics, the p -adic number systems were first described by Kurt Hensel in 1897

Prime knots

In knot theory, a prime knot is a knot which is, in a certain sense, indecomposable. In Mathematics, knot theory is the area of Topology that studies mathematical knots While inspired by knots which appear in daily life in shoelaces In Mathematics, a knot is an Embedding of a Circle in 3-dimensional Euclidean space, R 3 considered up to continuous deformations Specifically, it is one which cannot be written as the knot sum of two nontrivial knots. In Mathematics, specifically in Topology, the operation of connected sum is a geometric modification on Manifolds Its effect is to join two given manifolds

Open questions

There are many open questions about prime numbers. A very significant one is the Riemann hypothesis, which essentially says that the primes are as regularly distributed as possible. The Riemann hypothesis (also called the Riemann zeta-hypothesis) first formulated by Bernhard Riemann in 1859 is one of the most famous and important unsolved From a physical viewpoint, it roughly states that the irregularity in the distribution of primes only comes from random noise. From a mathematical viewpoint, it roughly states that the asymptotic distribution of primes (about 1/ log x of numbers less than x are primes, the prime number theorem) also holds for much shorter intervals of length about the square root of x (for intervals near x). This hypothesis is generally believed to be correct, in particular, the simplest assumption is that primes should have no significant irregularities without good reason.

Many famous conjectures appear to have a very high probability of being true (in a formal sense, many of them follow from simple heuristic probabilistic arguments):

Prime Euclid numbers: It is not known whether or not there are an infinite number of prime Euclid numbers. In Mathematics, Euclid numbers are Integers of the form E n = p n # + 1 where p

Strong Goldbach conjecture: Every even integer greater than 2 can be written as a sum of two primes. Goldbach's conjecture is one of the oldest unsolved problems in Number theory and in all of Mathematics.

Weak Goldbach conjecture: Every odd integer greater than 5 can be written as a sum of three primes. In Number theory, Goldbach's weak conjecture, also known as the odd Goldbach conjecture, the ternary Goldbach problem, or the 3-primes problem

Twin prime conjecture: There are infinitely many twin primes, pairs of primes with difference 2. The twin prime conjecture is a famous unsolved problem in Number theory that involves Prime numbers It states There are infinitely many primes A twin prime is a Prime number that differs from another prime number by Two.

Polignac's conjecture: For every positive integer n, there are infinitely many pairs of consecutive primes which differ by 2n. In Number theory, Polignac's conjecture was made by Alphonse de Polignac in 1849 and states For any positive even number n, there When n = 1 this is the twin prime conjecture.

A weaker form of Polignac's conjecture: Every even number is the difference of two primes. In Mathematics, the parity of an object states whether it is even or odd

It is widely believed there are infinitely many Mersenne primes, but not Fermat primes. In Mathematics, a Mersenne number is a positive integer that is one less than a Power of two: M_n=2^n-1 In Mathematics, a Fermat number, named after Pierre de Fermat who first studied them is a positive integer of the form F_{n} = 2^{2^{ ^[14]

It is conjectured there are infinitely many primes of the form n² + 1. ^[15]

Many well-known conjectures are special cases of the broad Schinzel's hypothesis H. In Mathematics, Schinzel 's hypothesis H is a very broad generalisation of Conjectures such as the Twin prime conjecture.

It is conjectured that there are infinitely many Fibonacci primes. A Fibonacci prime is a Fibonacci number that is prime. The first Fibonacci primes are: 2, 3, 5, 13 ^[16]

Legendre's conjecture: There is a prime number between n² and (n + 1)² for every positive integer n. Legendre's conjecture, proposed by Adrien-Marie Legendre, states that there is a Prime number between n 2 and ( n + 12

Cramér's conjecture: $\limsup_{n\rightarrow\infty} \frac{p_{n+1}-p_n}{(\log p_n)^2} = 1$ . In Number theory, Cramér's conjecture, formulated originally by the Swedish Mathematician Harald Cramér in 1936, states that \limsup_{n\rightarrow\infty} This conjecture implies Legendre's, but its status is more unsure.

Brocard's conjecture: There are always at least four primes between the squares of consecutive primes greater than 2. In Number theory, Brocard's conjecture is a Conjecture that there are at least four Prime numbers between ( p n)2

All four of Landau's problems from 1912 are listed above and still unsolved: Goldbach, twin primes, Legendre, n²+1 primes. At the 1912 International Congress of Mathematicians, Edmund Landau listed four basic problems about primes.

Applications

For a long time, number theory in general, and the study of prime numbers in particular, was seen as the canonical example of pure mathematics, with no applications outside of the self-interest of studying the topic. In particular, number theorists such as British mathematician G. H. Hardy prided themselves on doing work that had absolutely no military significance. The United Kingdom of Great Britain and Northern Ireland, commonly known as the United Kingdom, the UK or Britain,is a Sovereign state located Godfrey Harold Hardy FRS ( February 7, 1877 Cranleigh, Surrey, England &ndash December 1, 1947 ^[17] However, this vision was shattered in the 1970s, when it was publicly announced that prime numbers could be used as the basis for the creation of public key cryptography algorithms. Public-key cryptography, also known as asymmetric cryptography, is a form of Cryptography in which the key used to encrypt a message differs from the key Prime numbers are also used for hash tables and pseudorandom number generators. In Computer science, a hash table, or a hash map, is a Data structure that associates keys with values. A pseudorandom number generator ( PRNG) is an Algorithm for generating a sequence of numbers that approximates the properties of random numbers

Some rotor machines were designed with a different number of pins on each rotor, with the number of pins on any one rotor either prime, or coprime to the number of pins on any other rotor. In Cryptography, a rotor machine is an electro-mechanical device used for encrypting and decrypting secret messages In Mathematics, the Integers a and b are said to be coprime or relatively prime if they have no common factor other than This helped generate the full cycle of possible rotor positions before repeating any position. A full cycle is a mathematical term that represents a traversal over a set of non-random numbers

Public-key cryptography

Main article: public key cryptography

Several public-key cryptography algorithms, such as RSA, are based on large prime numbers (for example with 512 bits). Public-key cryptography, also known as asymmetric cryptography, is a form of Cryptography in which the key used to encrypt a message differs from the key In Cryptography, RSA is an Algorithm for Public-key cryptography. A bit is a binary digit, taking a value of either 0 or 1 Binary digits are a basic unit of Information storage and communication

Prime numbers in nature

Many numbers occur in nature, and inevitably some of these are prime. There are, however, relatively few examples of numbers that appear in nature because they are prime. For example, most starfish have 5 arms, and 5 is a prime number. Starfish (also called sea stars) are any Echinoderms belonging to the class Asteroidea. However there is no evidence to suggest that starfish have 5 arms because 5 is a prime number. Indeed, some starfish have different numbers of arms. Echinaster luzonicus normally has six arms, Luidia senegalensis has nine arms, and Solaster endeca can have as many as twenty arms. Why the majority of starfish (and most other echinoderms) have five-fold symmetry remains a mystery. Echinoderms (Phylum Echinodermata) are a phylum of marine Animals (including Sea stars) "Bilateral symmetry" redirects here For bilateral symmetry in mathematics see Reflection symmetry.

One example of the use of prime numbers in nature is as an evolutionary strategy used by cicadas of the genus Magicicada. A cicada is an Insect of the order Hemiptera, suborder Auchenorrhyncha, in the superfamily Cicadoidea, with large eyes wide apart on the Magicicada is the genus of the 13- and 17- year periodical Cicadas of eastern North America. ^[18] These insects spend most of their lives as grubs underground. A larva ( Latin; plural larvae) is a juvenile form of Animal with indirect development, undergoing Metamorphosis (for example They only pupate and then emerge from their burrows after 13 or 17 years, at which point they fly about, breed, and then die after a few weeks at most. The logic for this is believed to be that the prime number intervals between emergences makes it very difficult for predators to evolve that could specialise as predators on Magicicadas. ^[19] If Magicicadas appeared at a non-prime number intervals, say every 12 years, then predators appearing every 2, 3, 4, 6, or 12 years would be sure to meet them. Over a 200-year period, average predator populations during hypothetical outbreaks of 14- and 15-year cicadas would be up to 2% higher than during outbreaks of 13- and 17-year cicadas. ^[20] Though small, this advantage appears to have been enough to drive natural selection in favour of a prime-numbered life-cycle for these insects.

There is speculation that the zeros of the zeta function are connected to the energy levels of complex quantum systems. ^[21]

Prime numbers in the arts and literature

Prime numbers have influenced many artists and writers. The French composer Olivier Messiaen used prime numbers to create ametrical music through "natural phenomena". A composer (literally meaning 'one who puts together' is a person who creates Music, usually in the medium of notation, for Interpretation and Performance Olivier Messiaen ( December 10 1908 &ndash April 27 1992 was a French Composer, organist and ornithologist. In works such as La Nativité du Seigneur (1935) and Quatre études de rythme (1949-50), he simultaneously employs motifs with lengths given by different prime numbers to create unpredictable rhythms: the primes 41, 43, 47 and 53 appear in one of the études. According to Messiaen this way of composing was "inspired by the movements of nature, movements of free and unequal durations". ^[22]

In his science fiction novel Contact, later made into a film of the same name, the NASA scientist Carl Sagan suggested that prime numbers could be used as a means of communicating with aliens, an idea that he had first developed informally with American astronomer Frank Drake in 1975. Contact is a Science fiction Novel written by Carl Sagan and published in 1985. Contact is a 1997 Science fiction film adapted from the novel by Carl Sagan. The National Aeronautics and Space Administration ( NASA, ˈnæsə is an agency of the United States government, responsible for the nation's public space program Carl Edward Sagan ( November 9 1934 &ndash December 20 1996) was an American Astronomer, astrochemist, author Dr Frank Donald Drake (born May 28 1930, Chicago) is an American Astronomer and Astrophysicist. ^[23]

Tom Stoppard's award-winning 1993 play Arcadia was a conscious attempt to discuss mathematical ideas on the stage. Sir Tom Stoppard OM, CBE (born 3 July 1937 is a British Screenwriter playwright Arcadia is a 1993 play by Tom Stoppard concerning the relationship between past and present and between order and disorder and the certainty of knowledge In the opening scene, the 13 year old heroine puzzles over Fermat's last theorem, a theorem involving prime numbers. Fermat's Last Theorem is the name of the statement in Number theory that It is impossible to separate any power higher than the second into two like ^[24] ^[25] ^[26]

Many films reflect a popular fascination with the mysteries of prime numbers and cryptography: films such as Cube, Sneakers, The Mirror Has Two Faces and A Beautiful Mind, based on the biography of the mathematician and Nobel laureate John Forbes Nash by Sylvia Nasar. Cube is a 1997 Canadian Psychological thriller / horror / Science fiction movie directed by Vincenzo Sneakers is a 1992 caper Film directed by Phil Alden Robinson ( Field of Dreams) and written by Robinson The Mirror Has Two Faces is a 1996 American romantic Dramedy Film produced and directed by Barbra Streisand A Beautiful Mind is a 2001 American Biographical film about John Forbes Nash, the Nobel Laureate in Economics. Sylvia Nasar (born 17 August 1947 in Rosenheim, Germany) is a German economist and author best known for her biography of John Forbes ^[27] ^[28]

Notes

^ The Largest Known Prime by Year: A Brief History Prime Curios!: 17014…05727 (39-digits)
^ Hans Riesel, Prime Numbers and Computer Methods for Factorization. A full cycle is a mathematical term that represents a traversal over a set of non-random numbers In Mathematical logic, a Gödel numbering is a function that assigns to each symbol and Well-formed formula of some Formal language a unique In Mathematics, Hilbert number, named after David Hilbert, has different meanings In Mathematics, the adjective irreducible means that an object cannot be expressed as a product of at least two non-trivial factors in a given set In Mathematics, the logarithmic integral function or integral logarithm li( x) is a Special function. A polite number is a Positive integer which can be written as the sum of two or more consecutive positive integers A primality test is an Algorithm for determining whether an input number is prime. In Mathematics, a prime power is a Positive integer power of a Prime number. In Mathematical physics, the primon gas or free Riemann gas is a Toy model illustrating in a simple way some correspondences between Number theory The primorial has two similar but distinct meanings The name is attributed to Harvey Dubner and is a Portmanteau of prime and Factorial In Mathematics, a sphenic number ( Old Greek sphen = Wedge) is a positive integer which is the product of three distinct Prime The Ulam spiral, or prime spiral (in other languages also called the Ulam cloth) is a simple method of graphing the Prime numbers that reveals There are infinitely many Prime numbers Prime numbers may be generated with various Formulas for primes. New York: Springer (1994): 36
^ Richard K. Guy & John Horton Conway, The Book of Numbers. New York: Springer (1996): 129 - 130
^ Gowers, T (2002). William Timothy Gowers FRS (born 20 November 1963, Wiltshire) is a British mathematician Mathematics: A Very Short Introduction. Oxford University Press, 118. ISBN 0-19-285361-9. “The seemingly arbitrary exclusion of 1 from the definition of a prime … does not express some deep fact about numbers: it just happens to be a useful convention, adopted so there is only one way of factorizing any given number into primes”
^ ""Why is the number one not prime?"". Retrieved 2007-10-02.
^ ""Arguments for and against the primality of 1".
^ Letter in Latin from Goldbach to Euler, July 1730. Latin ( lingua Latīna, laˈtiːna is an Italic language, historically spoken in Latium and Ancient Rome.
^ P. Ribenboim: The Little Book of Bigger Primes, second edition, Springer, 2004, p. 4.
^ Furstenberg, Harry. (1955). "On the infinitude of primes". Amer. Math. Monthly 62 (5): 353. The American Mathematical Monthly ( is a mathematical journal founded by Benjamin Finkel in 1894. doi:10.2307/2307043. A digital object identifier ( DOI) is a permanent identifier given to an Electronic document.
^ Furstenberg's proof that there are infinitely many prime numbers. Everything2. Everything2, Everything2, or E2 for short is a collaborative Web -based community consisting of a database of interlinked user-submitted written Retrieved on 2006-11-26. Year 2006 ( MMVI) was a Common year starting on Sunday of the Gregorian calendar. Events 43 BC - The Second Triumvirate alliance of Gaius Julius Caesar Octavianus ("Octavian" later "Caesar Augustus"
^ The Top Twenty: Primorial
^ The Top Twenty: Factorial
^ The RSA Factoring Challenge — RSA Laboratories
^ E. g. , see Guy, Richard K. (1981), Unsolved Problems in Number Theory, Springer-Verlag , problem A3, pp. 7–8.
^ Eric W. Weisstein, Landau's Problems at MathWorld. Eric W Weisstein (born March 18, 1969, in Bloomington Indiana) is an Encyclopedist who created and maintains MathWorld MathWorld is an online Mathematics reference work created and largely written by Eric W
^ Caldwell, Chris, The Top Twenty: Lucas Number at The Prime Pages. The Prime Pages is a website about Prime numbers maintained by Prof
^ Hardy, G.H. (1940). Godfrey Harold Hardy FRS ( February 7, 1877 Cranleigh, Surrey, England &ndash December 1, 1947 A Mathematician's Apology. A Mathematician's Apology is a 1940 essay by British mathematician G Cambridge University Press. Cambridge University Press (known colloquially as CUP is a Publisher given a Royal Charter by Henry VIII in 1534 ISBN 0-521-42706-1. “No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years”
^ Goles, E. , Schulz, O. and M. Markus (2001). "Prime number selection of cycles in a predator-prey model", Complexity 6(4): 33-38
^ Paulo R. A. Campos, Viviane M. de Oliveira, Ronaldo Giro, and Douglas S. Galvão. (2004). "Emergence of Prime Numbers as the Result of Evolutionary Strategy". Phys. Rev. Lett. 93. Physical Review Letters is one of the most prestigious journals in Physics. doi:10.1103/PhysRevLett.93.098107. A digital object identifier ( DOI) is a permanent identifier given to an Electronic document.
^ Invasion of the Brood. The Economist (May 6, 2004). The Economist is an English-language weekly news and International affairs publication owned by The Economist Newspaper Ltd and edited in London Events 1527 - Spanish and German troops sack Rome; some consider this the end of the Renaissance. "MMIV" redirects here For the Modest Mouse album see " Baron von Bullshit Rides Again " Retrieved on 2006-11-26. Year 2006 ( MMVI) was a Common year starting on Sunday of the Gregorian calendar. Events 43 BC - The Second Triumvirate alliance of Gaius Julius Caesar Octavianus ("Octavian" later "Caesar Augustus"
^ Ivars Peterson (June 28, 1999). Events 1098 - Fighters of the First Crusade defeat Kerbogha of Mosul. Year 1999 ( MCMXCIX) was a Common year starting on Friday (link will display full 1999 Gregorian calendar) The Return of Zeta. MAA Online. Retrieved on 2008-3-14.
^ The Messiaen companion', ed. Peter Hill, Amadeus Press, 1994. ISBN 0-931340-95-0
^ Carl Pomerance, Prime Numbers and the Search for Extraterrestrial Intelligence, Retrieved on December 22, 2007
^ Tom Stoppard, Arcadia, Faber and Faber, 1993. Carl Pomerance (born in 1944 in Joplin, Missouri) is a well known number theorist. Events 1790 - The Turkish fortress of Izmail is stormed and captured by Suvorov and his Russian armies Year 2007 ( MMVII) was a Common year starting on Monday of the Gregorian calendar in the 21st century. ISBN 0-571-16934-1.
^ The Cambridge Companion to Tom Stoppard, ed. Katherine E. Kelly, Cambridge University Press, 2001. ISBN 0521645921
^ The Mathematics of Arcadia, an event involving Tom Stoppard and MSRI in the University of California, Berkeley
^ Music of the Spheres, Marcus du Sautoy's selection of films featuring prime numbers
^ A Beautiful Mind

References

John Derbyshire, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. The Mathematical Sciences Research Institute (MSRI, founded in 1982, is a mathematical research institution whose funding sources include the National The University of California Berkeley (also referred to as Cal, Berkeley and UC Berkeley) is a major research university located in Berkeley Marcus Peter Francis du Sautoy (born August 26, 1965) is a Professor of Mathematics at the University of Oxford. Joseph Henry Press; 448 pages
Wladyslaw Narkiewicz, The development of prime number theory. From Euclid to Hardy and Littlewood. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2000.
H. Riesel, Prime Numbers and Computer Methods for Factorization, 2nd ed. , Birkhäuser 1994.
Marcus du Sautoy, The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics. HarperCollins; 352 pages. ISBN 0-06-621070-4. The Music of Primes website.
Karl Sabbagh, The Riemann Hypothesis: The Greatest Unsolved Problem in Mathematics. Farrar, Straus and Giroux; 340 pages

External links

Caldwell, Chris, The Prime Pages at primes.utm.edu. The Prime Pages is a website about Prime numbers maintained by Prof
Prime Numbers at MathWorld
Prime sequencing technologies
MacTutor history of prime numbers
The prime puzzles
An English translation of Euclid's proof that there are infinitely many primes
Number Spiral with prime patterns
An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier
EFF Cooperative Computing Awards
Why a Number Is Prime by Enrique Zeleny, The Wolfram Demonstrations Project.

Prime number generators & calculators

Online Prime Number Generator and Checker - instantly checks and finds prime numbers up to 128 digits long (does NOT require Java or Javascript)
Prime number calculator — Check prime number, and find next largest and next smallest prime numbers (requires Javascript).
Fast Online primality test — Dario Alpern's personal site – Makes use of the Elliptic Curve Method (up to thousands digits numbers check!, requires Java)
Prime Number Generator — Generates a given number of primes above a given start number.
Primes from WIMS is an online prime generator.
Huge database of prime numbers

Dictionary

-noun

(number theory) Any natural number greater than 1 divisible only by itself and 1.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

History of prime numbers