A
prime number is a
natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
greater than 1 that has no positive
divisorIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
s other than 1 and itself. A natural number greater than 1 that is not a prime number is called a
composite numberA composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2 and 3 in addition to 1 and 6. The
fundamental theorem of arithmeticIn number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
establishes the central role of primes in
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
: any integer greater than 1 can be expressed as a product of primes that is unique
up toIn mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...
ordering. This theorem requires excluding 1 as a prime.
The property of being prime is called primality. A simple but slow method of verifying the primality of a given number
n is known as
trial divisionTrial division is the most laborious but easiest to understand of the integer factorization algorithms. Its ease of implementation makes it a viable integer factorization option for devices with little available memory, such as graphing calculators....
. It consists of testing whether
n is a multiple of any integer between 2 and . Algorithms that are much more efficient than trial division have been devised to test the primality of large numbers. Particularly fast methods are available for primes of special forms, such as
Mersenne primeIn mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...
s. , the largest known prime number has nearly 13 million
decimal digitsA digit is a symbol used in combinations to represent numbers in positional numeral systems. The name "digit" comes from the fact that the 10 digits of the hands correspond to the 10 symbols of the common base 10 number system, i.e...
.
There are
infinitely many primes, as
demonstrated by EuclidEuclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. There are several well-known proofs of the theorem.-Euclid's proof:...
around 300 BC. There is no known useful formula that yields all of the prime numbers and no composites. However, the distribution of primes, that is to say, the statistical behaviour of primes in the large, can be modeled. The first result in that direction is the
prime number theoremIn number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....
, proven at the end of the 19th century, which says that the
probabilityProbability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
that a given, randomly chosen number is prime is inversely
proportionalIn mathematics, two variable quantities are proportional if one of them is always the product of the other and a constant quantity, called the coefficient of proportionality or proportionality constant. In other words, are proportional if the ratio \tfrac yx is constant. We also say that one...
to its number of digits, or the
logarithmThe logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
of
n.
Many questions around prime numbers remain open, such as
Goldbach's conjectureGoldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:A Goldbach number is a number that can be expressed as the sum of two odd primes...
, which asserts that every even integer greater than 2 can be expressed as the sum of two primes, and the
twin primeA twin prime is a prime number that differs from another prime number by two. Except for the pair , this is the smallest possible difference between two primes. Some examples of twin prime pairs are , , , , and...
conjecture, which says that there are infinitely many pairs of primes whose difference is 2. Such questions spurred the development of various branches of number theory, focusing on
analyticIn mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Dirichlet's introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic...
or
algebraicAlgebraic number theory is a major branch of number theory which studies algebraic structures related to algebraic integers. This is generally accomplished by considering a ring of algebraic integers O in an algebraic number field K/Q, and studying their algebraic properties such as factorization,...
aspects of numbers. Primes are used in several routines in
information technologyInformation technology is the acquisition, processing, storage and dissemination of vocal, pictorial, textual and numerical information by a microelectronics-based combination of computing and telecommunications...
, such as
public-key cryptographyPublic-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
, which makes use of properties such as the difficulty of factoring large numbers into their prime factors. Prime numbers give rise to various generalizations in other mathematical domains, mainly
algebraAlgebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
, such as
prime elementIn abstract algebra, an element p of a commutative ring R is said to be prime if it is not zero, not a unit and whenever p divides ab for some a and b in R, then p divides a or p divides b...
s and
prime idealIn algebra , a prime ideal is a subset of a ring which shares many important properties of a prime number in the ring of integers...
s.
Definition and examples
A
natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
- 1, 2, 3, 4, 5, 6, ...
is called a
prime or a
prime number if it is greater than 1 and has exactly two
divisorIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
s, 1 and the number itself. Natural numbers greater than 1 that are not prime are called
compositeA composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
.
Among the numbers 1 to 6, the numbers 2, 3, and 5 are the prime numbers, while 1, 4, and 6 are not prime. 1 is excluded as a prime number, for reasons explained below. 2 is a prime number, since the only natural numbers dividing it are 1 and 2. Next, 3 is prime, too: 1 and 3 do divide 3 without remainder, but 3 divided by 2 gives
remainderIn arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....
1. Thus, 3 is prime. However, 4 is composite, since 2 is another number (in addition to 1 and 4) dividing 4 without remainder:
- 4 = 2 · 2.
5 is again prime: none of the numbers 2, 3, or 4 divide 5. Next, 6 is divisible by 2 or 3, since
- 6 = 2 · 3.
Hence, 6 is not prime. The image at the right illustrates that 12 is not prime: 12 = 3 · 4. In general, no even number greater than 2 is prime: any such number has at least three distinct divisors, namely 1, 2, and . This implies that is not prime. Accordingly, the term
odd prime refers to any prime number greater than 2. In a similar vein, all prime numbers bigger than 5, written in the usual
decimalThe decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
system, end in 1, 3, 7, or 9, since even numbers are multiples of 2 and numbers ending in 0 or 5 are multiples of 5.
If is a natural number, then 1 and divide without remainder. Therefore, the condition of being a prime can also be restated as: a number is prime if it is greater than one and if none of
divides (without remainder). Yet another way to say the same is: a number is prime if it cannot be written as a product of two integers and , both of which are larger than 1:
- .
In other words, is prime if items cannot be divided up into smaller equal-size groups of more than one item.
The smallest 168 prime numbers (all the prime numbers under 1000) are:
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 .
The set of all primes is often denoted .
The fundamental theorem of arithmetic
The crucial importance of prime numbers to
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
and mathematics in general stems from the
fundamental theorem of arithmetic, which states that every positive integer larger than 1 can be written as a product of one or more primes in a way that is
uniqueIn 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 mathematical logic, this sort of quantification is known as uniqueness quantification or unique existential quantification.Uniqueness quantification is...
except possibly for the order of the prime
factorsIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
. Primes can thus be considered the “basic building blocks” of the natural numbers. For example:
| 23244 |
= 2 · 2 · 3 · 13 · 149 |
| |= 22 · 3 · 13 · 149. (22 denotes the square or second power of 2.) |
As in this example, the same prime factor may occur multiple times. A decomposition:
of a number into (finitely many) prime factors , , ... to is called
prime factorization of . The fundamental theorem of arithmetic can be rephrased so as to say that any factorization into primes will be identical except for the order of the factors. So, albeit there are many
prime factorizationIn number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
algorithms to do this in practice for larger numbers, they all have to yield the same result.
If is a prime number and divides a product of integers, then divides or divides . This proposition is known as
Euclid's lemmaIn mathematics, Euclid's lemma is an important lemma regarding divisibility and prime numbers. In its simplest form, the lemma states that a prime number that divides a product of two integers must divide one of the two integers...
. It is used in some proofs of the uniqueness of prime factorizations.
Primality of one
Most early Greeks did not even consider 1 to be a number, so did not consider it a prime. In the 19th century however, many mathematicians did consider the number 1 a prime. For example,
Derrick Norman LehmerDerrick Norman Lehmer was an American mathematician and number theorist....
's list of primes up to 10,006,721, reprinted as late as 1956, started with 1 as its first prime.
Henri LebesgueHenri Léon Lebesgue was a French mathematician most famous for his theory of integration, which was a generalization of the seventeenth century concept of integration—summing the area between an axis and the curve of a function defined for that axis...
is said to be the last professional mathematician to call 1 prime. Although a large body of mathematical work is also valid when calling 1 a prime, the above fundamental theorem of arithmetic does not hold as stated. For example, the number 15 can be factored as or . If 1 were admitted as a prime, these two presentations would be considered different factorizations of 15 into prime numbers, so the statement of that theorem would have to be modified. Furthermore, the prime numbers have several properties that the number 1 lacks, such as the relationship of the number to its corresponding value of
Euler's totient functionIn number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n 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 n that...
or the sum of divisors function.
History
There are hints in the surviving records of the
ancient EgyptAncient Egypt was an ancient civilization of Northeastern Africa, concentrated along the lower reaches of the Nile River in what is now the modern country of Egypt. Egyptian civilization coalesced around 3150 BC with the political unification of Upper and Lower Egypt under the first pharaoh...
ians 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. However, the earliest surviving records of the explicit study of prime numbers come from the
Ancient GreeksAncient Greece is a civilization belonging to a period of Greek history that lasted from the Archaic period of the 8th to 6th centuries BC to the end of antiquity. Immediately following this period was the beginning of the Early Middle Ages and the Byzantine era. Included in Ancient Greece is the...
.
Euclid's ElementsEuclid's Elements is a mathematical and geometric treatise consisting of 13 books written by the Greek mathematician Euclid in Alexandria c. 300 BC. It is a collection of definitions, postulates , propositions , and mathematical proofs of the propositions...
(circa 300 BC) contain important theorems about primes, including the
infinitude of primesEuclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. There are several well-known proofs of the theorem.-Euclid's proof:...
and the
fundamental theorem of arithmeticIn number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
. Euclid also showed how to construct a
perfect numberIn number theory, a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself . Equivalently, a perfect number is a number that is half the sum of all of its positive divisors i.e...
from a
Mersenne primeIn mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-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.
After the Greeks, little happened with the study of prime numbers until the 17th century. In 1640
Pierre de FermatPierre de Fermat was a French lawyer at the Parlement of Toulouse, France, and an amateur mathematician who is given credit for early developments that led to infinitesimal calculus, including his adequality...
stated (without proof)
Fermat's little theoremFermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
(later proved by Leibniz and
EulerLeonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...
). 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
2n + 1 are prime (they are called
Fermat numbers) and he verified this up to
n = 4 (or 2
16 + 1). However, the very next Fermat number 2
32 + 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 MersenneMarin Mersenne, Marin Mersennus or le Père Mersenne was a French theologian, philosopher, mathematician and music theorist, often referred to as the "father of acoustics"...
looked at primes of the form 2
p − 1, with
p a prime. They are called Mersenne primes in his honor.
Euler's work in number theory included many results about primes. He showed the infinite series
{{redirect|Prime}}
A prime number (or a prime) is a natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
greater than 1 that has no positive
divisorIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
s other than 1 and itself. A natural number greater than 1 that is not a prime number is called a
composite numberA composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2 and 3 in addition to 1 and 6. The
fundamental theorem of arithmeticIn number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
establishes the central role of primes in
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
: any integer greater than 1 can be expressed as a product of primes that is unique
up toIn mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...
ordering. This theorem requires excluding 1 as a prime.
The property of being prime is called primality. A simple but slow method of verifying the primality of a given number
n is known as
trial divisionTrial division is the most laborious but easiest to understand of the integer factorization algorithms. Its ease of implementation makes it a viable integer factorization option for devices with little available memory, such as graphing calculators....
. It consists of testing whether
n is a multiple of any integer between 2 and {{radical|
n}}. Algorithms that are much more efficient than trial division have been devised to test the primality of large numbers. Particularly fast methods are available for primes of special forms, such as
Mersenne primeIn mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...
s. {{As of|2011}}, the largest known prime number has nearly 13 million
decimal digitsA digit is a symbol used in combinations to represent numbers in positional numeral systems. The name "digit" comes from the fact that the 10 digits of the hands correspond to the 10 symbols of the common base 10 number system, i.e...
.
There are
infinitely many primes, as
demonstrated by EuclidEuclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. There are several well-known proofs of the theorem.-Euclid's proof:...
around 300 BC. There is no known useful formula that yields all of the prime numbers and no composites. However, the distribution of primes, that is to say, the statistical behaviour of primes in the large, can be modeled. The first result in that direction is the
prime number theoremIn number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....
, proven at the end of the 19th century, which says that the
probabilityProbability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
that a given, randomly chosen number {{math|
n}} is prime is inversely
proportionalIn mathematics, two variable quantities are proportional if one of them is always the product of the other and a constant quantity, called the coefficient of proportionality or proportionality constant. In other words, are proportional if the ratio \tfrac yx is constant. We also say that one...
to its number of digits, or the
logarithmThe logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
of
n.
Many questions around prime numbers remain open, such as
Goldbach's conjectureGoldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:A Goldbach number is a number that can be expressed as the sum of two odd primes...
, which asserts that every even integer greater than 2 can be expressed as the sum of two primes, and the
twin primeA twin prime is a prime number that differs from another prime number by two. Except for the pair , this is the smallest possible difference between two primes. Some examples of twin prime pairs are , , , , and...
conjecture, which says that there are infinitely many pairs of primes whose difference is 2. Such questions spurred the development of various branches of number theory, focusing on
analyticIn mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Dirichlet's introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic...
or
algebraicAlgebraic number theory is a major branch of number theory which studies algebraic structures related to algebraic integers. This is generally accomplished by considering a ring of algebraic integers O in an algebraic number field K/Q, and studying their algebraic properties such as factorization,...
aspects of numbers. Primes are used in several routines in
information technologyInformation technology is the acquisition, processing, storage and dissemination of vocal, pictorial, textual and numerical information by a microelectronics-based combination of computing and telecommunications...
, such as
public-key cryptographyPublic-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
, which makes use of properties such as the difficulty of factoring large numbers into their prime factors. Prime numbers give rise to various generalizations in other mathematical domains, mainly
algebraAlgebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
, such as
prime elementIn abstract algebra, an element p of a commutative ring R is said to be prime if it is not zero, not a unit and whenever p divides ab for some a and b in R, then p divides a or p divides b...
s and
prime idealIn algebra , a prime ideal is a subset of a ring which shares many important properties of a prime number in the ring of integers...
s.
Definition and examples
A
natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
- 1, 2, 3, 4, 5, 6, ...
is called a
prime or a
prime number if it is greater than 1 and has exactly two
divisorIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
s, 1 and the number itself. Natural numbers greater than 1 that are not prime are called
compositeA composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
.
Among the numbers 1 to 6, the numbers 2, 3, and 5 are the prime numbers, while 1, 4, and 6 are not prime. 1 is excluded as a prime number, for reasons explained below. 2 is a prime number, since the only natural numbers dividing it are 1 and 2. Next, 3 is prime, too: 1 and 3 do divide 3 without remainder, but 3 divided by 2 gives
remainderIn arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....
1. Thus, 3 is prime. However, 4 is composite, since 2 is another number (in addition to 1 and 4) dividing 4 without remainder:
- 4 = 2 · 2.
5 is again prime: none of the numbers 2, 3, or 4 divide 5. Next, 6 is divisible by 2 or 3, since
- 6 = 2 · 3.
Hence, 6 is not prime. The image at the right illustrates that 12 is not prime: {{nowrap begin}}12 = 3 · 4{{nowrap end}}. In general, no even number greater than 2 is prime: any such number {{math|
n}} has at least three distinct divisors, namely 1, 2, and {{math|
n}}. This implies that {{math|
n}} is not prime. Accordingly, the term
odd prime refers to any prime number greater than 2. In a similar vein, all prime numbers bigger than 5, written in the usual
decimalThe decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
system, end in 1, 3, 7, or 9, since even numbers are multiples of 2 and numbers ending in 0 or 5 are multiples of 5.
If {{math|
n}} is a natural number, then 1 and {{math|
n}} divide {{math|
n}} without remainder. Therefore, the condition of being a prime can also be restated as: a number is prime if it is greater than one and if none of
- {{math|2, 3, ..., n − 1}}
divides {{math|
n}} (without remainder). Yet another way to say the same is: a number {{math|
n > 1}} is prime if it cannot be written as a product of two integers {{math|
a}} and {{math|
b}}, both of which are larger than 1:
- {{math|1=n = a · b}}.
In other words, {{math|
n}} is prime if {{math|
n}} items cannot be divided up into smaller equal-size groups of more than one item.
The smallest 168 prime numbers (all the prime numbers under 1000) are:
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 {{OEIS|id=A000040}}.
The set of all primes is often denoted {{math|
P}}.
The fundamental theorem of arithmetic
{{Main|Fundamental theorem of arithmetic}}
The crucial importance of prime numbers to
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
and mathematics in general stems from the
fundamental theorem of arithmetic, which states that every positive integer larger than 1 can be written as a product of one or more primes in a way that is
uniqueIn 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 mathematical logic, this sort of quantification is known as uniqueness quantification or unique existential quantification.Uniqueness quantification is...
except possibly for the order of the prime
factorsIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
. Primes can thus be considered the “basic building blocks” of the natural numbers. For example:
| 23244 |
= 2 · 2 · 3 · 13 · 149 |
| |= 22 · 3 · 13 · 149. (22 denotes the square or second power of 2.) |
As in this example, the same prime factor may occur multiple times. A decomposition:
- {{math|1=n = p1 · p2 · ... · pt}}
of a number {{math|
n}} into (finitely many) prime factors {{math|
p1}}, {{math|
p2}}, ... to {{math|
pt}} is called
prime factorization of {{math|
n}}. The fundamental theorem of arithmetic can be rephrased so as to say that any factorization into primes will be identical except for the order of the factors. So, albeit there are many
prime factorizationIn number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
algorithms to do this in practice for larger numbers, they all have to yield the same result.
If {{math|
p}} is a prime number and {{math|
p}} divides a product {{math|
ab}} of integers, then {{math|
p}} divides {{math|
a}} or {{math|
p}} divides {{math|
b}}. This proposition is known as
Euclid's lemmaIn mathematics, Euclid's lemma is an important lemma regarding divisibility and prime numbers. In its simplest form, the lemma states that a prime number that divides a product of two integers must divide one of the two integers...
. It is used in some proofs of the uniqueness of prime factorizations.
Primality of one
Most early Greeks did not even consider 1 to be a number, so did not consider it a prime. In the 19th century however, many mathematicians did consider the number 1 a prime. For example,
Derrick Norman LehmerDerrick Norman Lehmer was an American mathematician and number theorist....
's list of primes up to 10,006,721, reprinted as late as 1956, started with 1 as its first prime.
Henri LebesgueHenri Léon Lebesgue was a French mathematician most famous for his theory of integration, which was a generalization of the seventeenth century concept of integration—summing the area between an axis and the curve of a function defined for that axis...
is said to be the last professional mathematician to call 1 prime. Although a large body of mathematical work is also valid when calling 1 a prime, the above fundamental theorem of arithmetic does not hold as stated. For example, the number 15 can be factored as {{nowrap|3 · 5}} or {{nowrap| 1 · 3 · 5}}. If 1 were admitted as a prime, these two presentations would be considered different factorizations of 15 into prime numbers, so the statement of that theorem would have to be modified. Furthermore, the prime numbers have several properties that the number 1 lacks, such as the relationship of the number to its corresponding value of
Euler's totient functionIn number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n 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 n that...
or the sum of divisors function.
History
There are hints in the surviving records of the
ancient EgyptAncient Egypt was an ancient civilization of Northeastern Africa, concentrated along the lower reaches of the Nile River in what is now the modern country of Egypt. Egyptian civilization coalesced around 3150 BC with the political unification of Upper and Lower Egypt under the first pharaoh...
ians 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. However, the earliest surviving records of the explicit study of prime numbers come from the
Ancient GreeksAncient Greece is a civilization belonging to a period of Greek history that lasted from the Archaic period of the 8th to 6th centuries BC to the end of antiquity. Immediately following this period was the beginning of the Early Middle Ages and the Byzantine era. Included in Ancient Greece is the...
.
Euclid's ElementsEuclid's Elements is a mathematical and geometric treatise consisting of 13 books written by the Greek mathematician Euclid in Alexandria c. 300 BC. It is a collection of definitions, postulates , propositions , and mathematical proofs of the propositions...
(circa 300 BC) contain important theorems about primes, including the
infinitude of primesEuclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. There are several well-known proofs of the theorem.-Euclid's proof:...
and the
fundamental theorem of arithmeticIn number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
. Euclid also showed how to construct a
perfect numberIn number theory, a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself . Equivalently, a perfect number is a number that is half the sum of all of its positive divisors i.e...
from a
Mersenne primeIn mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-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.
After the Greeks, little happened with the study of prime numbers until the 17th century. In 1640
Pierre de FermatPierre de Fermat was a French lawyer at the Parlement of Toulouse, France, and an amateur mathematician who is given credit for early developments that led to infinitesimal calculus, including his adequality...
stated (without proof)
Fermat's little theoremFermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
(later proved by Leibniz and
EulerLeonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...
). 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
2n + 1 are prime (they are called
Fermat numbers) and he verified this up to
n = 4 (or 2
16 + 1). However, the very next Fermat number 2
32 + 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 MersenneMarin Mersenne, Marin Mersennus or le Père Mersenne was a French theologian, philosopher, mathematician and music theorist, often referred to as the "father of acoustics"...
looked at primes of the form 2
p − 1, with
p a prime. They are called Mersenne primes in his honor.
Euler's work in number theory included many results about primes. He showed the infinite series
{{redirect|Prime}}
A prime number (or a prime) is a natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
greater than 1 that has no positive
divisorIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
s other than 1 and itself. A natural number greater than 1 that is not a prime number is called a
composite numberA composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2 and 3 in addition to 1 and 6. The
fundamental theorem of arithmeticIn number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
establishes the central role of primes in
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
: any integer greater than 1 can be expressed as a product of primes that is unique
up toIn mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...
ordering. This theorem requires excluding 1 as a prime.
The property of being prime is called primality. A simple but slow method of verifying the primality of a given number
n is known as
trial divisionTrial division is the most laborious but easiest to understand of the integer factorization algorithms. Its ease of implementation makes it a viable integer factorization option for devices with little available memory, such as graphing calculators....
. It consists of testing whether
n is a multiple of any integer between 2 and {{radical|
n}}. Algorithms that are much more efficient than trial division have been devised to test the primality of large numbers. Particularly fast methods are available for primes of special forms, such as
Mersenne primeIn mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...
s. {{As of|2011}}, the largest known prime number has nearly 13 million
decimal digitsA digit is a symbol used in combinations to represent numbers in positional numeral systems. The name "digit" comes from the fact that the 10 digits of the hands correspond to the 10 symbols of the common base 10 number system, i.e...
.
There are
infinitely many primes, as
demonstrated by EuclidEuclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. There are several well-known proofs of the theorem.-Euclid's proof:...
around 300 BC. There is no known useful formula that yields all of the prime numbers and no composites. However, the distribution of primes, that is to say, the statistical behaviour of primes in the large, can be modeled. The first result in that direction is the
prime number theoremIn number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....
, proven at the end of the 19th century, which says that the
probabilityProbability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
that a given, randomly chosen number {{math|
n}} is prime is inversely
proportionalIn mathematics, two variable quantities are proportional if one of them is always the product of the other and a constant quantity, called the coefficient of proportionality or proportionality constant. In other words, are proportional if the ratio \tfrac yx is constant. We also say that one...
to its number of digits, or the
logarithmThe logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
of
n.
Many questions around prime numbers remain open, such as
Goldbach's conjectureGoldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:A Goldbach number is a number that can be expressed as the sum of two odd primes...
, which asserts that every even integer greater than 2 can be expressed as the sum of two primes, and the
twin primeA twin prime is a prime number that differs from another prime number by two. Except for the pair , this is the smallest possible difference between two primes. Some examples of twin prime pairs are , , , , and...
conjecture, which says that there are infinitely many pairs of primes whose difference is 2. Such questions spurred the development of various branches of number theory, focusing on
analyticIn mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Dirichlet's introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic...
or
algebraicAlgebraic number theory is a major branch of number theory which studies algebraic structures related to algebraic integers. This is generally accomplished by considering a ring of algebraic integers O in an algebraic number field K/Q, and studying their algebraic properties such as factorization,...
aspects of numbers. Primes are used in several routines in
information technologyInformation technology is the acquisition, processing, storage and dissemination of vocal, pictorial, textual and numerical information by a microelectronics-based combination of computing and telecommunications...
, such as
public-key cryptographyPublic-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
, which makes use of properties such as the difficulty of factoring large numbers into their prime factors. Prime numbers give rise to various generalizations in other mathematical domains, mainly
algebraAlgebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
, such as
prime elementIn abstract algebra, an element p of a commutative ring R is said to be prime if it is not zero, not a unit and whenever p divides ab for some a and b in R, then p divides a or p divides b...
s and
prime idealIn algebra , a prime ideal is a subset of a ring which shares many important properties of a prime number in the ring of integers...
s.
Definition and examples
A
natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
- 1, 2, 3, 4, 5, 6, ...
is called a
prime or a
prime number if it is greater than 1 and has exactly two
divisorIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
s, 1 and the number itself. Natural numbers greater than 1 that are not prime are called
compositeA composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
.
Among the numbers 1 to 6, the numbers 2, 3, and 5 are the prime numbers, while 1, 4, and 6 are not prime. 1 is excluded as a prime number, for reasons explained below. 2 is a prime number, since the only natural numbers dividing it are 1 and 2. Next, 3 is prime, too: 1 and 3 do divide 3 without remainder, but 3 divided by 2 gives
remainderIn arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....
1. Thus, 3 is prime. However, 4 is composite, since 2 is another number (in addition to 1 and 4) dividing 4 without remainder:
- 4 = 2 · 2.
5 is again prime: none of the numbers 2, 3, or 4 divide 5. Next, 6 is divisible by 2 or 3, since
- 6 = 2 · 3.
Hence, 6 is not prime. The image at the right illustrates that 12 is not prime: {{nowrap begin}}12 = 3 · 4{{nowrap end}}. In general, no even number greater than 2 is prime: any such number {{math|
n}} has at least three distinct divisors, namely 1, 2, and {{math|
n}}. This implies that {{math|
n}} is not prime. Accordingly, the term
odd prime refers to any prime number greater than 2. In a similar vein, all prime numbers bigger than 5, written in the usual
decimalThe decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
system, end in 1, 3, 7, or 9, since even numbers are multiples of 2 and numbers ending in 0 or 5 are multiples of 5.
If {{math|
n}} is a natural number, then 1 and {{math|
n}} divide {{math|
n}} without remainder. Therefore, the condition of being a prime can also be restated as: a number is prime if it is greater than one and if none of
- {{math|2, 3, ..., n − 1}}
divides {{math|
n}} (without remainder). Yet another way to say the same is: a number {{math|
n > 1}} is prime if it cannot be written as a product of two integers {{math|
a}} and {{math|
b}}, both of which are larger than 1:
- {{math|1=n = a · b}}.
In other words, {{math|
n}} is prime if {{math|
n}} items cannot be divided up into smaller equal-size groups of more than one item.
The smallest 168 prime numbers (all the prime numbers under 1000) are:
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 {{OEIS|id=A000040}}.
The set of all primes is often denoted {{math|
P}}.
The fundamental theorem of arithmetic
{{Main|Fundamental theorem of arithmetic}}
The crucial importance of prime numbers to
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
and mathematics in general stems from the
fundamental theorem of arithmetic, which states that every positive integer larger than 1 can be written as a product of one or more primes in a way that is
uniqueIn 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 mathematical logic, this sort of quantification is known as uniqueness quantification or unique existential quantification.Uniqueness quantification is...
except possibly for the order of the prime
factorsIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
. Primes can thus be considered the “basic building blocks” of the natural numbers. For example:
| 23244 |
= 2 · 2 · 3 · 13 · 149 |
| |= 22 · 3 · 13 · 149. (22 denotes the square or second power of 2.) |
As in this example, the same prime factor may occur multiple times. A decomposition:
- {{math|1=n = p1 · p2 · ... · pt}}
of a number {{math|
n}} into (finitely many) prime factors {{math|
p1}}, {{math|
p2}}, ... to {{math|
pt}} is called
prime factorization of {{math|
n}}. The fundamental theorem of arithmetic can be rephrased so as to say that any factorization into primes will be identical except for the order of the factors. So, albeit there are many
prime factorizationIn number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
algorithms to do this in practice for larger numbers, they all have to yield the same result.
If {{math|
p}} is a prime number and {{math|
p}} divides a product {{math|
ab}} of integers, then {{math|
p}} divides {{math|
a}} or {{math|
p}} divides {{math|
b}}. This proposition is known as
Euclid's lemmaIn mathematics, Euclid's lemma is an important lemma regarding divisibility and prime numbers. In its simplest form, the lemma states that a prime number that divides a product of two integers must divide one of the two integers...
. It is used in some proofs of the uniqueness of prime factorizations.
Primality of one
Most early Greeks did not even consider 1 to be a number, so did not consider it a prime. In the 19th century however, many mathematicians did consider the number 1 a prime. For example,
Derrick Norman LehmerDerrick Norman Lehmer was an American mathematician and number theorist....
's list of primes up to 10,006,721, reprinted as late as 1956, started with 1 as its first prime.
Henri LebesgueHenri Léon Lebesgue was a French mathematician most famous for his theory of integration, which was a generalization of the seventeenth century concept of integration—summing the area between an axis and the curve of a function defined for that axis...
is said to be the last professional mathematician to call 1 prime. Although a large body of mathematical work is also valid when calling 1 a prime, the above fundamental theorem of arithmetic does not hold as stated. For example, the number 15 can be factored as {{nowrap|3 · 5}} or {{nowrap| 1 · 3 · 5}}. If 1 were admitted as a prime, these two presentations would be considered different factorizations of 15 into prime numbers, so the statement of that theorem would have to be modified. Furthermore, the prime numbers have several properties that the number 1 lacks, such as the relationship of the number to its corresponding value of
Euler's totient functionIn number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n 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 n that...
or the sum of divisors function.
History
There are hints in the surviving records of the
ancient EgyptAncient Egypt was an ancient civilization of Northeastern Africa, concentrated along the lower reaches of the Nile River in what is now the modern country of Egypt. Egyptian civilization coalesced around 3150 BC with the political unification of Upper and Lower Egypt under the first pharaoh...
ians 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. However, the earliest surviving records of the explicit study of prime numbers come from the
Ancient GreeksAncient Greece is a civilization belonging to a period of Greek history that lasted from the Archaic period of the 8th to 6th centuries BC to the end of antiquity. Immediately following this period was the beginning of the Early Middle Ages and the Byzantine era. Included in Ancient Greece is the...
.
Euclid's ElementsEuclid's Elements is a mathematical and geometric treatise consisting of 13 books written by the Greek mathematician Euclid in Alexandria c. 300 BC. It is a collection of definitions, postulates , propositions , and mathematical proofs of the propositions...
(circa 300 BC) contain important theorems about primes, including the
infinitude of primesEuclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. There are several well-known proofs of the theorem.-Euclid's proof:...
and the
fundamental theorem of arithmeticIn number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
. Euclid also showed how to construct a
perfect numberIn number theory, a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself . Equivalently, a perfect number is a number that is half the sum of all of its positive divisors i.e...
from a
Mersenne primeIn mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-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.
After the Greeks, little happened with the study of prime numbers until the 17th century. In 1640
Pierre de FermatPierre de Fermat was a French lawyer at the Parlement of Toulouse, France, and an amateur mathematician who is given credit for early developments that led to infinitesimal calculus, including his adequality...
stated (without proof)
Fermat's little theoremFermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
(later proved by Leibniz and
EulerLeonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...
). 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
2n + 1 are prime (they are called
Fermat numbers) and he verified this up to
n = 4 (or 2
16 + 1). However, the very next Fermat number 2
32 + 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 MersenneMarin Mersenne, Marin Mersennus or le Père Mersenne was a French theologian, philosopher, mathematician and music theorist, often referred to as the "father of acoustics"...
looked at primes of the form 2
p − 1, with
p a prime. They are called Mersenne primes in his honor.
Euler's work in number theory included many results about primes. He showed the infinite series
{{nowrap is
divergentIn mathematics, a divergent series is an infinite series that is not convergent, meaning that the infinite sequence of the partial sums of the series does not have a limit....
.
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.
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
asymptoticIn analytic geometry, an asymptote of a curve is a line such that the distance between the curve and the line approaches zero as they tend to infinity. Some sources include the requirement that the curve may not cross the line infinitely often, but this is unusual for modern authors...
to
x/ln(
x), where ln(
x) is the
natural logarithmThe natural logarithm is the logarithm to the base e, where e is an irrational and transcendental constant approximately equal to 2.718281828...
of
x. Ideas of Riemann in his
1859 paper on the zeta-function die Anzahl der Primzahlen unter einer gegebenen is a seminal 8-page paper by Bernhard Riemann published in the November 1859 edition of the Monatsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin.Although it is the only paper he ever published on number theory, it...
sketched a program that would lead to a proof of the prime number theorem. This outline was completed by
HadamardJacques Salomon Hadamard FRS was a French mathematician who made major contributions in number theory, complex function theory, differential geometry and partial differential equations.-Biography:...
and de la Vallée Poussin, who independently proved the
prime number theoremIn number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....
in 1896.
Proving a number is prime is not done (for large numbers) by trial division. Many mathematicians have worked on
primality testA primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...
s for large numbers, often restricted to specific number forms. This includes
Pépin's testIn mathematics, Pépin's test is a primality test, which can be used to determine whether a Fermat number is prime. It is a variant of Proth's test. The test is named for a French mathematician, Théophile Pépin.-Description of the test:...
for Fermat numbers (1877),
Proth's theoremIn number theory, Proth's theorem is a primality test for Proth numbers.It states that if p is a Proth number, of the form k2n + 1 with k odd and k In number theory, Proth's theorem is a primality test for Proth numbers....
(around 1878), the Lucas–Lehmer primality test (originated 1856), and the generalized Lucas primality test. More recent algorithms like APRT-CL,
ECPPElliptic Curve Primality Proving is a method based on elliptic curves to prove the primality of a number . It is a general-purpose algorithm, meaning it does not depend on the number being of a special form...
, and
AKSThe AKS primality test is a deterministic primality-proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, on August 6, 2002, in a paper titled "PRIMES is in P"...
work on arbitrary numbers but remain much slower.
For a long time, prime numbers were thought to have extremely limited application outside of
pure mathematicsBroadly speaking, pure mathematics is mathematics which studies entirely abstract concepts. From the eighteenth century onwards, this was a recognized category of mathematical activity, sometimes characterized as speculative mathematics, and at variance with the trend towards meeting the needs of...
;{{Citation needed|date=August 2008}} this changed in the 1970s when the concepts of
public-key cryptographyPublic-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
were invented, in which prime numbers formed the basis of the first algorithms such as the RSA cryptosystem algorithm.
Since 1951 all the
largest known primeThe largest known prime number is the largest integer that is currently known to be a prime number.It was proven by Euclid that there are infinitely many prime numbers; thus, there is always a prime greater than the largest known prime. Many mathematicians and hobbyists search for large prime numbers...
s have been found by
computerA computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
s. The search for ever larger primes has generated interest outside mathematical circles. The
Great Internet Mersenne Prime SearchThe Great Internet Mersenne Prime Search is a collaborative project of volunteers who use freely available computer software to search for Mersenne prime numbers. The project was founded by George Woltman, who also wrote the software Prime95 and MPrime for the project...
and other
distributed computingDistributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
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 number of prime numbers
{{Main|Euclid's theorem}}
There are infinitely many prime numbers. Another way of saying this is that the sequence
- 2, 3, 5, 7, 11, 13, ...
of prime numbers never ends. This statement is referred to as
Euclid's theorem in honor of the ancient Greek mathematician
EuclidEuclid , fl. 300 BC, also known as Euclid of Alexandria, was a Greek mathematician, often referred to as the "Father of Geometry". He was active in Alexandria during the reign of Ptolemy I...
, since the first known proof for this statement is attributed to him. Many more proofs of the infinitude of primes are known, including an
analyticalMathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and measure, limits, infinite series, and analytic functions...
proof by Euler,
Goldbach'sChristian Goldbach was a German mathematician who also studied law. He is remembered today for Goldbach's conjecture.-Biography:...
proof based on
Fermat numbers, Fürstenberg's
proof using general topologyIn number theory, Hillel Fürstenberg's proof of the infinitude of primes is a celebrated topological proof that the integers contain infinitely many prime numbers. When examined closely, the proof is less a statement about topology than a statement about certain properties of arithmetic sequences....
, and
Kummer'sErnst Eduard Kummer was a German mathematician. Skilled in applied mathematics, Kummer trained German army officers in ballistics; afterwards, he taught for 10 years in a gymnasium, the German equivalent of high school, where he inspired the mathematical career of Leopold Kronecker.-Life:Kummer...
elegant proof.
Euclid's proof
Euclid's proof (Book IX, Proposition 20) begins with the definition of prime and then considers any finite set of primes, which we denote
p1,
p2, up to
pn. The key idea is to consider the product of all these numbers plus one (this number is called a
Euclid numberIn mathematics, Euclid numbers are integers of the form En = pn# + 1, where pn# is the primorial of pn which is the nth prime. They are named after the ancient Greek mathematician Euclid....
):
- P = p1 · p2 · ... · pn + 1.
Like any natural number,
P can be written as a product of prime numbers; this is assured by the fundamental theorem of arithmetic:
- P = q1 · q2 · ... · qm
(it is possible that
P itself is prime, in which case
m = 1).
None of the primes
p1,
p2, etc., to
pn can divide
P, because dividing
P by any of these leaves a remainder of 1. Therefore the primes
q1,
q2, ...,
qm are additional primes beyond the ones we started with. Thus any finite set of primes can be extended to a larger finite set of primes.
The Euclid number
P does not need to be prime, for example
- 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30,031 = 59 · 509 (both primes).
It is often erroneously reported that Euclid proved the infinitude of primes by contradiction, beginning with the assumption that the set initially considered contains all prime numbers, or that it contains precisely the
n smallest primes, rather than any arbitrary finite set of primes.
Euler's analytical proof
Euler's proof uses the sum of the
reciprocalsIn mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity, 1. The multiplicative inverse of a fraction a/b is b/a. For the multiplicative inverse of a real number, divide 1 by the...
of primes,
This sum becomes bigger than any arbitrary
real numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
provided that
p is big enough. This shows that there are infinitely many primes, since otherwise this sum would grow only until the biggest prime
p is reached. The growth of
S(
p) is quantified by
Mertens' second theoremIn number theory, Mertens' theorems are three 1874 results related to the density of prime numbers proved by Franz Mertens...
. For comparison, the sums
do not grow to infinity, when
n grows. In this sense, prime numbers occur more often than squares of natural numbers.
Brun's theoremIn number theory, Brun's theorem was proved by Viggo Brun in 1919. It states that the sum of the reciprocals of the twin primes is convergent with a finite value known as Brun's constant, usually denoted by B2...
states that the sum of the reciprocals of
twin primeA twin prime is a prime number that differs from another prime number by two. Except for the pair , this is the smallest possible difference between two primes. Some examples of twin prime pairs are , , , , and...
s,
is finite.
Testing primality and integer factorization
There are various methods to determine whether a given number
n is prime. The most basic routine, trial division is of little practical use because of its slowness. One group of modern primality tests is applicable to arbitrary numbers, while more efficient tests are available for particular numbers. Most such methods only tell whether
n is prime or not. Routines also yielding one (or all) prime factors of
n are called
factorizationIn number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
algorithms.
Trial division
The most basic method of checking the primality of a given integer
n is called
trial divisionTrial division is the most laborious but easiest to understand of the integer factorization algorithms. Its ease of implementation makes it a viable integer factorization option for devices with little available memory, such as graphing calculators....
. This routine consists of dividing
n by each integer
m that is greater than 1 and less than or equal to the
square rootIn mathematics, a square root of a number x is a number r such that r2 = x, or, in other words, a number r whose square is x...
of
n. If the result of any of these divisions is an integer, then
n is not a prime, otherwise it is a prime. Indeed, if {{nowrap|
n {{=}}
ab}} is composite (with
a and
b ≠ 1) then one of the factors
a or
b is necessarily at most √{{overline|
n}}. For example, for {{nowrap|
n {{=}} 37}}, the trial divisions are by {{nowrap|
m {{=}} 2, 3, 4, 5, and 6.}} None of these numbers divides 37, so 37 is prime. This routine can be implemented more efficiently if a complete list of primes up to √{{overline|
n}} is known—then trial divisions need to be checked only for those
m that are prime. For example, to check the primality of 37, only three divisions are necessary (
m = 2, 3, and 5), given that 4 and 6 are composite.
While a simple method, trial division quickly becomes impractical for testing large integers because the number of possible factors grows too rapidly as
n increases. According to the prime number theorem explained below, the number of prime numbers less than √{{overline|
n}} is approximately given by {{nowrap|√{{overline|
n}} / ln(√{{overline|
n}})}}, so the algorithm may need up to this number of trial divisions to check the primality of
n. For {{nowrap|
n {{=}} 10
20}}, this number is 450 million—too large for many practical applications.
Sieves
An algorithm yielding all primes up to a given limit, such as required in the trial division method, is called a
sieveSieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The primordial example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the primordial example of a...
. The oldest example, the
sieve of EratosthenesIn mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
(see above) is useful for relatively small primes. The modern
sieve of AtkinIn mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. It is an optimized version of the ancient sieve of Eratosthenes, but does some preliminary work and then marks off multiples of primes squared, rather than multiples of primes. ...
is more complicated, but faster when properly optimized. Before the advent of computers, lists of primes up to bounds like 10
7 were also used.
Primality testing vs. primality proving
Modern primality tests for general numbers
n can be divided into two main classes, probabilistic (or "Monte Carlo") and
deterministic algorithmIn computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
s. The former merely "test" whether
n is prime in the sense that they declare
n to be (definitely) composite or "
probably primeIn number theory, a probable prime is an integer that satisfies a specific condition also satisfied by all prime numbers. Different types of probable primes have different specific conditions...
", the latter meaning that
n may or may not be a prime number. Composite numbers that do pass a given primality test are referred to as
pseudoprimeIn number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.- Definition :...
s. For example, Fermat's primality test relies on
Fermat's little theoremFermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
. This theorem says that for any prime number
p and any integer
a not divisible by
p, {{nowrap|
ap − 1 − 1}} is divisible by
p. Thus, if {{nowrap|
an − 1 − 1}} is not divisible by
n,
n cannot be prime. However,
n may be composite even if this divisibility holds. In fact, there are infinitely many composite numbers
n that pass the Fermat primality test for every choice of
a that is coprime with
n (
Carmichael numbers), for example {{nowrap|
n {{=}} 561}}.
Deterministic algorithms do not erroneously report composite numbers as prime. In practice, the fastest such method is known as
elliptic curve primality provingElliptic Curve Primality Proving is a method based on elliptic curves to prove the primality of a number . It is a general-purpose algorithm, meaning it does not depend on the number being of a special form...
. Analyzing its run time is based on
heuristic argumentA heuristic argument is an argument that reasons from the value of a method or principle that has been shown by experimental investigation to be a useful aid in learning, discovery and problem-solving. A widely-used and important example of a heuristic argument is Occam's Razor....
s, as opposed to the
rigorously provenIn mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
complexity of the more recent
AKS primality testThe AKS primality test is a deterministic primality-proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, on August 6, 2002, in a paper titled "PRIMES is in P"...
. Deterministic methods are typically slower than probabilistic ones, so the latter ones are typically applied first before a more time-consuming deterministic routine is employed.
The following table lists a number of prime tests. The running time is given in terms of
n, the number to be tested and, for probabilistic algorithms, the number
k of tests performed. Moreover, ε is an arbitrarily small positive number, and log is the
logarithmThe logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
to an unspecified base. The
big O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
means that, for example, elliptic curve primality proving requires a time that is bounded by a factor (not depending on
n, but on ε) times log
5+ε(
n).
| Test |
Developed in |
Type |
Running time |
Notes |
| AKS primality test The AKS primality test is a deterministic primality-proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, on August 6, 2002, in a paper titled "PRIMES is in P"...
|
2002 |
deterministic |
O(log6+ε(n)) |
|
| Elliptic curve primality proving Elliptic Curve Primality Proving is a method based on elliptic curves to prove the primality of a number . It is a general-purpose algorithm, meaning it does not depend on the number being of a special form...
|
1977 |
deterministic |
O(log5+ε(n)) heuristically |
|
| Miller–Rabin primality test |
1980 |
probabilistic |
O(k · log2+ε (n)) |
error probability 4−k |
| Solovay–Strassen primality test |
1977 |
probabilistic |
O(k · log3 n) |
error probability 2−k |
| Fermat primality test The Fermat primality test is a probabilistic test to determine if a number is probable prime.-Concept:Fermat's little theorem states that if p is prime and 1 \le a...
|
|
probabilistic |
O(k · log2+ε (n)) |
fails for Carmichael numbers |
Special-purpose algorithms and the largest known prime
{{See|List of prime numbers}}
In addition to the aforementioned tests applying to any natural number
n, a number of much more efficient primality tests is available for special numbers. For example, to run Lucas' primality test requires the knowledge of the prime factors of {{nowrap|
n − 1}}, while the Lucas–Lehmer primality test needs the prime factors of {{nowrap|
n + 1}} as input. For example, these tests can be applied to check whether
- n!
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
± 1 = 1 · 2 · 3 · ... · n ± 1
are prime. Prime numbers of this form are known as
factorial primeA factorial prime is a prime number that is one less or one more than a factorial . The first few factorial primes are:n! − 1 is prime for :n! + 1 is prime for :...
s. Other primes where either
p + 1 or
p − 1 is of a particular shape include the
Sophie Germain primeIn number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. For example, 23 is a Sophie Germain prime because it is a prime and 2 × 23 + 1 = 47, and 47 is also a prime number...
s (primes of the form 2
p + 1 with
p prime),
primorial primeIn mathematics, primorial primes are prime numbers of the form pn# ± 1, where:The first few primorial primes are, the largest known primorial prime is 843301# - 1 with 365,851 digits, found in 2010 by the PrimeGrid project....
s, Fermat primes and
Mersenne primeIn mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...
s, that is, prime numbers that are of the form {{nowrap|2
p − 1}}, where
p is an arbitrary prime. The Lucas–Lehmer test is particularly fast for numbers of this form. This is why the
largest known primeThe largest known prime number is the largest integer that is currently known to be a prime number.It was proven by Euclid that there are infinitely many prime numbers; thus, there is always a prime greater than the largest known prime. Many mathematicians and hobbyists search for large prime numbers...
has almost always been a Mersenne prime since the dawn of electronic computers.
Fermat primes are of the form {{nowrap|
Fk {{=}} 2
2k + 1}}, with
k an arbitrary natural number. They are named after
Pierre de FermatPierre de Fermat was a French lawyer at the Parlement of Toulouse, France, and an amateur mathematician who is given credit for early developments that led to infinitesimal calculus, including his adequality...
who conjectured that all such numbers
Fk are prime. This was based on the evidence of the first five numbers in this series—3, 5, 17,
257Year 257 was a common year starting on Thursday of the Julian calendar. At the time, it was known as the Year of the Consulship of Valerianus and Gallienus...
, and 65,537—being prime. However,
F6 is composite and so are all other Fermat numbers that have been verified as of 2011. A
regular n-gonA regular polygon is a polygon that is equiangular and equilateral . Regular polygons may be convex or star.-General properties:...
is
constructible using straightedge and compassIn mathematics, a constructible polygon is a regular polygon that can be constructed with compass and straightedge. For example, a regular pentagon is constructible with compass and straightedge while a regular heptagon is not....
if and only if
- n = 2i · m
where
m is a product of any number of distinct Fermat primes and
i is any natural number, including zero.
The following table gives the largest known primes of the mentioned types. Some of these primes have been found using
distributed computingDistributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
. In 2009, the
Great Internet Mersenne Prime SearchThe Great Internet Mersenne Prime Search is a collaborative project of volunteers who use freely available computer software to search for Mersenne prime numbers. The project was founded by George Woltman, who also wrote the software Prime95 and MPrime for the project...
project was awarded a US$100,000 prize for first discovering a prime with at least 10 million digits. The
Electronic Frontier FoundationThe Electronic Frontier Foundation is an international non-profit digital rights advocacy and legal organization based in the United States...
also offers $150,000 and $250,000 for primes with at least 100 million digits and 1 billion digits, respectively. 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].
| Type |
Prime |
Number of decimal digits |
Date |
Found by |
Mersenne primeIn mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...
|
243,112,609 − 1 |
12,978,189 |
August 23, 2008 |
Great Internet Mersenne Prime Search |
| not a Mersenne prime (Proth number) |
19,249 × 213,018,586 + 1 |
3,918,990 |
March 26, 2007 |
Seventeen or Bust Seventeen or Bust is a distributed computing project started in March 2002 to solve the last seventeen cases in the Sierpinski problem.-Goals:...
|
| factorial prime A factorial prime is a prime number that is one less or one more than a factorial . The first few factorial primes are:n! − 1 is prime for :n! + 1 is prime for :...
|
94550! − 1 |
429,390 |
October 2010 |
Domanov, PrimeGrid PrimeGrid is a distributed computing project for searching for prime numbers of world-record size. It makes use of the Berkeley Open Infrastructure for Network Computing platform...
|
| primorial prime In mathematics, primorial primes are prime numbers of the form pn# ± 1, where:The first few primorial primes are, the largest known primorial prime is 843301# - 1 with 365,851 digits, found in 2010 by the PrimeGrid project....
|
843301# - 1 |
365,851 |
December 2010 |
PrimeGrid PrimeGrid is a distributed computing project for searching for prime numbers of world-record size. It makes use of the Berkeley Open Infrastructure for Network Computing platform...
|
| twin prime A twin prime is a prime number that differs from another prime number by two. Except for the pair , this is the smallest possible difference between two primes. Some examples of twin prime pairs are , , , , and...
s |
65516468355 × 2333333 ± 1 |
100,355 |
2009 |
Twin prime search Twin Prime Search is a distributed computing project that looks for large twin primes. It uses the programs LLR and NewPGen . It was founded on April 13, 2006 by Michael Kwok...
|
Integer factorization
{{main|Integer factorization}}
Given a composite integer
n, the task of providing one (or all) prime factors is referred to as
factorization of
n. Elliptic curve factorization is an algorithm relying on arithmetic on an
elliptic curveIn mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...
.
Distribution
In 1975, number theorist
Don ZagierDon Bernard Zagier is an American mathematician whose main area of work is number theory. He is currently one of the directors of the Max Planck Institute for Mathematics in Bonn, Germany, and a professor at the Collège de France in Paris, France.He was born in Heidelberg, Germany...
commented that primes both
{{Cquote|grow like weeds among the natural numbers, seeming to obey no other law than that of chance [but also] exhibit stunning regularity [and] that there are laws governing their behavior, and that they obey these laws with almost military precision.}}
The distribution of primes in the large, such as the question how many primes are smaller than a given, large threshold, is described by the prime number theorem, but no efficient
formula for the n-th primeIn number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is easily computable is presently known...
is known. Dirichlet's theorem on arithmetic progressions quantifies how often linear polynomials
(with integers
a and
b) take prime values. The corresponding question for quadratic polynomials is less well-understood.
Formulas for primes
{{main|formulas for primes}}
There is no known efficient formula for primes. For example, Mills' theorem and a theorem of
WrightSir Edward Maitland Wright was an English mathematician.He is best known for co-authoring “Hardy and Wright”, An Introduction to the Theory of Numbers, with G. H...
assert that there are real constants
A and μ such that
are prime for any natural number
n. Here
represents the
floor functionIn mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following integer, respectively...
, i.e., largest integer not greater than the number in question. The latter formula can be shown using
Bertrand's postulate (proven first by Chebyshev), which states that there always exists at least one prime number
p with
n <
p < 2
n − 2, for any natural number
n > 3. However, computing
A or μ requires the knowledge of infintely many primes to begin with. Another formula is based on
Wilson's theorem and generates the number 2 many times and all other primes exactly once.
There is no non-constant
polynomialIn mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
, even in several variables, that takes
only prime values. However, 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. This can be used to obtain a single formula with the property that all its
positive values are prime.
Number of prime numbers below a given number
{{Main|Prime number theorem}}
The
prime counting functionIn mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number x. It is denoted by \scriptstyle\pi .-History:...
π(
n) is defined as the number of primes up to
n. For example π(11) = 5, since there are five primes less than or equal to 11. There are known
algorithmIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s to compute exact values of π(
n) faster than it would be possible to compute each prime up to
n. The
prime number theorem states that π(
n) is approximately given by
in the sense that the ratio of π(
n) and the right hand fraction approaches 1 when
n grows to infinity. This implies that the likelihood that a number less than
n is prime is (approximately) inversely proportional to the number of digits in
n. A more accurate estimate for π(
n) is given by the offset logarithmic integral
The prime number theorem also implies estimates for the size of the
n-th prime number
pn (i.e.,
p1 = 2,
p2 = 3, etc.): up to a bounded factor,
pn grows like {{nowrap|
n log(
n)}}. In particular, the
prime gaps, i.e. the differences {{nowrap|
pn −
pn−1}} of two consecutive primes, become arbitrarily large. This latter statement can also be seen in a more elementary way by noting that the sequence {{nowrap|
n! + 2,
n! + 3, …,
n! +
n}} (for the notation
n! read
factorialIn mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
) consists of {{nowrap|
n − 1}} composite numbers, for any natural number
n.
Arithmetic progressions
An
arithmetic progressionIn mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant...
is the set of natural numbers that give the same remainder when divided by some fixed number
q called
modulusIn mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
. For example,
- 3, 12, 21, 30, 39, ...,
is an arithmetic progression modulo {{nowrap|
q {{=}} 9}}. Except for 3, none of these numbers is prime, since {{nowrap|3 + 9
n {{=}} 3(1 + 3
n)}} so that the remaining numbers in this progression are all composite. (In general terms, all prime numbers above
q are of the form
q#In mathematics, and more particularly in number theory, primorial is a function from natural numbers to natural numbers similar to the factorial function, but rather than multiplying successive positive integers, only successive prime numbers are multiplied...
·
n +
m, where 0 <
m <
q#, and
m has no prime factor ≤
q.) Thus, the progression
- a, {{nowrap|a + q,}} {{nowrap|a + 2q,}} {{nowrap|a + 3q, …}}
can have infinitely many primes only when
a and
q are
coprimeIn number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
, i.e., their
greatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
is one. If this necessary condition is satisfied,
Dirichlet's theorem on arithmetic progressionsIn number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n ≥ 0. In other words, there are infinitely many primes which are...
asserts that the progression contains infinitely many primes. The picture below illustrates this with {{nowrap|
q {{=}} 9}}: the numbers are "wrapped around" as soon as a multiple of 9 is passed. Primes are highlighted in red. The rows (=progressions) starting with {{nowrap|
a {{=}} 3}}, 6, or 9 contain at most one prime number. In all other rows ({{nowrap|
a {{=}} 1}}, 2, 4, 5, 7, and 8) there are infinitely many prime numbers. What is more, the primes are distributed equally among those rows in the long run—the density of all primes congruent
a modulo 9 is 1/6.
The Green–Tao theorem shows that there are arbitrarily long arithmetic progressions consisting of primes.
An odd prime
p is expressible as the sum of two squares, {{nowrap|
p {{=}}
x2 +
y2}}, exactly if
p is congruent 1 modulo 4 (
Fermat's theorem on sums of two squares).
Prime values of quadratic polynomials
Euler noted that the function
gives prime numbers for {{nowrap|0 ≤
n < 40}}, a fact leading into deep
algebraic number theoryAlgebraic number theory is a major branch of number theory which studies algebraic structures related to algebraic integers. This is generally accomplished by considering a ring of algebraic integers O in an algebraic number field K/Q, and studying their algebraic properties such as factorization,...
, more specifically
Heegner numberIn number theory, a Heegner number is a square-free positive integer d such that the imaginary quadratic field Q has class number 1...
s. For bigger
n, it does take composite values. The Hardy-Littlewood conjecture F makes an asymptotic prediction about the density of primes among the values of
quadratic polynomialIn mathematics, a quadratic polynomial or quadratic is a polynomial of degree two, also called second-order polynomial. That means the exponents of the polynomial's variables are no larger than 2...
s (with integer
coefficientIn mathematics, a coefficient is a multiplicative factor in some term of an expression ; it is usually a number, but in any case does not involve any variables of the expression...
s
a,
b, and
c)
in terms of Li(
n) and the coefficients
a,
b, and
c. However, progress has proved hard to come by: no quadratic polynomial (with {{nowrap|
a ≠ 0}}) is known to take infinitely many prime values. The
Ulam spiralThe Ulam spiral, or prime spiral is a simple method of visualizing the prime numbers that reveals the apparent tendency of certain quadratic polynomials to generate unusually large numbers of primes...
depicts all natural numbers in a spiral-like way. Surprisingly, prime numbers cluster on certain diagonals and not others, suggesting that some quadratic polynomials take prime values more often than other ones.
The zeta function and the Riemann hypothesis
{{Main|Riemann hypothesis}}
The
Riemann zeta function ζ(
s) is defined as an
infinite sumA series is the sum of the terms of a sequence. Finite sequences and series have defined first and last terms, whereas infinite sequences and series continue indefinitely....
where
s is a
complex numberA complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
with real part bigger than 1. It is a consequence of the fundamental theorem of arithmetic that this sum agrees with the
infinite product
The zeta function is closely related to prime numbers. For example, the aforementioned fact that there are infinitely many primes can also be seen using the zeta function: if there were only finitely many primes then ζ(1) would have a finite value. However, the
harmonic seriesIn mathematics, the harmonic series is the divergent infinite series:Its name derives from the concept of overtones, or harmonics in music: the wavelengths of the overtones of a vibrating string are 1/2, 1/3, 1/4, etc., of the string's fundamental wavelength...
{{nowrap|1 + 1/2 + 1/3 + 1/4 + ...}}
divergesIn mathematics, a divergent series is an infinite series that is not convergent, meaning that the infinite sequence of the partial sums of the series does not have a limit....
(i.e., exceeds any given number), so there must be infinitely many primes. Another example of the richness of the zeta function and a glimpse of modern
algebraic number theoryAlgebraic number theory is a major branch of number theory which studies algebraic structures related to algebraic integers. This is generally accomplished by considering a ring of algebraic integers O in an algebraic number field K/Q, and studying their algebraic properties such as factorization,...
is the following identity (
Basel problemThe Basel problem is a famous problem in mathematical analysis with relevance to number theory, first posed by Pietro Mengoli in 1644 and solved by Leonhard Euler in 1735. Since the problem had withstood the attacks of the leading mathematicians of the day, Euler's solution brought him immediate...
), due to Euler,
The reciprocal of ζ(2), 6/π
2, is the
probabilityProbability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
that two numbers selected at random are
relatively primeIn number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
.
The unproven
Riemann hypothesis, dating from 1859, states that except for {{nowrap|
s {{=}} −2, −4, ...,}} all zeroes of the ζ-function have real part equal to 1/2. The connection to prime numbers is that it essentially says that the primes are as regularly distributed as possible.{{Clarify|date=June 2011}} 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 theoremIn number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....
) 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.
Other conjectures
{{See|:Category:Conjectures about prime numbers}}
In addition to the Riemann hypothesis, many more conjectures revolving about primes have been posed. Often having an elementary formulation, many of these conjectures have withstood a proof for decades: all four of
Landau's problemsAt the 1912 International Congress of Mathematicians, Edmund Landau listed four basic problems about primes. These problems were characterised in his speech as "unattackable at the present state of science" and are now known as Landau's problems...
from 1912 are still unsolved. One of them is
Goldbach's conjectureGoldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:A Goldbach number is a number that can be expressed as the sum of two odd primes...
, which asserts that every even integer
n greater than 2 can be written as a sum of two primes. {{As of|February 2011}}, this conjecture has been verified for all numbers up to {{nowrap|
n {{=}} 2 · 10
17}}. Weaker statements than this have been proven, for example
Vinogradov's theoremIn number theory, Vinogradov's theorem implies that any sufficiently large odd integer can be written as a sum of three prime numbers. It is a weaker form of Goldbach's conjecture, which would imply the existence of such a representation for all odd integers greater than five. It is named after...
says that every sufficiently large odd integer greater can be written as a sum of three primes.
Chen's theoremright|thumb|Chen JingrunChen's theorem states that every sufficiently large even number can be written as the sum of either two primes, or a prime and a semiprime . The theorem was first stated by Chinese mathematician Chen Jingrun in 1966, with further details of the proof in 1973. His original...
says that every sufficiently large even number can be expressed as the sum of a prime and a
semiprimeIn mathematics, a semiprime is a natural number that is the product of two prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... ....
, the product of two primes. Also, any even integer can be written as the sum of six primes. The branch of number theory studying such questions is called
additive number theoryIn number theory, the specialty additive number theory studies subsets of integers and their behavior under addition. More abstractly, the field of "additive number theory" includes the study of Abelian groups and commutative semigroups with an operation of addition. Additive number theory has...
.
Other conjectures deal with the question whether an infinity of prime numbers subject to certain constraints exists. It is conjectured that there are infinitely many
Fibonacci primeA Fibonacci prime is a Fibonacci number that is prime, a type of integer sequence prime.The first Fibonacci primes are :-Known Fibonacci primes:It is not known if there are infinitely many Fibonacci primes...
s and infinitely many
Mersenne primeIn mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...
s, but not Fermat primes. It is not known whether or not there are an infinite number of
Wieferich primeIn number theory, a Wieferich prime is a prime number p such that p2 divides 2p − 1 − 1, therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides 2p − 1 − 1...
s and of prime
Euclid numberIn mathematics, Euclid numbers are integers of the form En = pn# + 1, where pn# is the primorial of pn which is the nth prime. They are named after the ancient Greek mathematician Euclid....
s.
A third type of conjectures concerns aspects of the distribution of primes. It is conjectured that there are infinitely many
twin primeA twin prime is a prime number that differs from another prime number by two. Except for the pair , this is the smallest possible difference between two primes. Some examples of twin prime pairs are , , , , and...
s, pairs of primes with difference 2 (twin prime conjecture).
Polignac's conjectureIn number theory, Polignac's conjecture was made by Alphonse de Polignac in 1849 and states:The conjecture has not been proven or disproven for any value of n....
is a strengthening of that conjecture, it states that for every positive integer
n, there are infinitely many pairs of consecutive primes that differ by 2
n. It is conjectured there are infinitely many primes of the form
n2 + 1. These conjectures are special cases of the broad
Schinzel's hypothesis HIn mathematics, Schinzel's hypothesis H is a very broad generalisation of conjectures such as the twin prime conjecture. It aims to define the possible scope of a conjecture of the nature that several sequences of the type...
.
Brocard's conjecture says that there are always at least four primes between the squares of consecutive primes greater than 2.
Legendre's conjectureLegendre's conjecture, proposed by Adrien-Marie Legendre, states that there is a prime number between n2 and 2 for every positive integer n. The conjecture is one of Landau's problems and unproven ....
states that there is a prime number between
n2 and (
n + 1)
2 for every positive integer
n. It is implied by the stronger
Cramér's conjecture.
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
BritishThe United Kingdom of Great Britain and Northern IrelandIn the United Kingdom and Dependencies, other languages have been officially recognised as legitimate autochthonous languages under the European Charter for Regional or Minority Languages...
mathematician
G. H. HardyGodfrey Harold “G. H.” Hardy FRS was a prominent English mathematician, known for his achievements in number theory and mathematical analysis....
prided themselves on doing work that had absolutely no military significance. 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. Prime numbers are also used for
hash tableIn computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
s and
pseudorandom number generatorA pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
s.
Some
rotor machineIn cryptography, a rotor machine is an electro-mechanical device used for encrypting and decrypting secret messages. Rotor machines were the cryptographic state-of-the-art for a prominent period of history; they were in widespread use in the 1920s–1970s...
s were designed with a different number of pins on each rotor, with the number of pins on any one rotor either prime, or
coprimeIn number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
to the number of pins on any other rotor. This helped generate the
full cycleA full cycle is a mathematical term that represents a traversal over a set of non-random numbers. A full cycle implies that every number in the set was chosen exactly once before repeating.Full cycles are useful in Pseudorandom number generators....
of possible rotor positions before repeating any position.
The
International Standard Book NumberThe International Standard Book Number is a unique numeric commercial book identifier based upon the 9-digit Standard Book Numbering code created by Gordon Foster, Emeritus Professor of Statistics at Trinity College, Dublin, for the booksellers and stationers W.H...
s work with a
check digitA check digit is a form of redundancy check used for error detection, the decimal equivalent of a binary checksum. It consists of a single digit computed from the other digits in the message....
, which exploits the fact that 11 is a prime.
Arithmetic modulo a prime and finite fields
{{Main|Modular arithmetic}}
Modular arithmetic modifies usual arithmetic by only using the numbers
where
n is a fixed natural number called modulus.
Calculating sums, differences and products is done as usual, but whenever a negative number or a number greater than
n−1 occurs, it gets replaced by the
remainderIn arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....
after division by
n. For instance, for
n = 7, the sum 3 + 5 is 1 instead of 8, since 8 divided by 7 has remainder 1. This is referred to by saying "3 + 5 is congruent to 1 modulo 7" and is denoted
Similarly, 6 + 1 ≡ 0 (mod 7), 2 − 5 ≡ 4 (mod 7), since −3 + 7 = 4, and 3 · 4 ≡ 5 (mod 7) as 12 has remainder 5. Standard properties of
additionAddition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....
and
multiplicationMultiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
familiar from the
integerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s remain valid in modular arithmetic. In the parlance of
abstract algebraAbstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
, the above set of integers, which is also denoted
Z/
nZ, is therefore a commutative ringIn ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra....
for any n
.
Divisionright|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
, however, is not in general possible in this setting. For example, for n
= 6, the equation
a solution x
of which would be an analogue of 2/3, cannot be solved, as one can see by calculating 3 · 0, ..., 3 · 5 modulo 6. The distinctive feature of prime numbers is the following: division is
possible in modular arithmetic if and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
n
is a prime. Equivalently, n
is prime if and only if all integers m
satisfying {{nowrap|2 ≤ m
≤ n
− 1}} are coprimeIn number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
to n
, i.e. their only common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
is one. Indeed, for n
= 7, the equation
has a unique solution, {{nowrap|x
{{=}} 3}}. Because of this, for any prime p
, Z/pZ (also denoted
Fp) is called a
fieldIn abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
or, more specifically, a
finite fieldIn abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
since it contains finitely many, namely
p, elements.
A number of theorems can be derived from inspecting
Fp in this abstract way. For example,
Fermat's little theoremFermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
, stating
for any integer
a not divisble by
p, may be proved using these notions. This implies
Giuga's conjecture says that this equation is also a sufficient condition for
p to be prime. Another consequence of Fermat's little theorem is the following: if
p is a prime number other than 2 and 5,
1/
p is always a recurring decimal, whose period is {{nowrap|
p − 1}} or a divisor of {{nowrap|
p − 1}}. The fraction
1/
p expressed likewise in base
q (rather than base 10) has similar effect, provided that
p is not a prime factor of
q.
Wilson's theorem says that an integer
p > 1 is prime if and only if the
factorialIn mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
(
p − 1)! + 1 is divisible by
p. Moreover, an integer
n > 4 is composite if and only if (
n − 1)
! is divisible by
n.
Other mathematical occurrences of primes
Many mathematical domains make great use of prime numbers. An example from the theory of
finite groupIn mathematics and abstract algebra, a finite group is a group whose underlying set G has finitely many elements. During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of...
s are the Sylow theorems: if
G is a finite group and
pn is the
highest power of the prime p that dividesIn number theory, for a given prime number p, the p-adic order or additive p-adic valuation of a number n is the highest exponent ν such that pν divides n. It is commonly abbreviated νp. The most important application of the p-adic order is in constructing the field of p-adic numbers...
the order of
G, then
G has a subgroup of order
pn. Also, any group of prime order is cyclic (
Lagrange's theoremLagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....
).
Public-key cryptography
{{main|Public key cryptography}}
Several public-key cryptography algorithms, such as RSA and the Diffie–Hellman key exchange, are based on large prime numbers (for example 512
bitA bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
primes are frequently used for RSA and 1024 bit primes are typical for Diffie–Hellman.). RSA relies on the fact that it is thought to be much easier (i.e., more efficient) to perform the multiplication of two (large) numbers
x and
y than to calculate
x and
y (assumed
coprimeIn number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
) if only the product
xy is known. The Diffie–Hellman key exchange relies on the fact that there are efficient algorithms for
modular exponentiationModular exponentiation is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography....
, while the reverse operation the
discrete logarithmIn mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
is thought to be a hard problem.
Prime numbers in nature
Inevitably, some of the numbers that occur in nature are prime. There are, however, relatively few examples of numbers that appear in nature
because they are prime.
One example of the use of prime numbers in nature is as an evolutionary strategy used by
cicadaA cicada is an insect of the order Hemiptera, suborder Auchenorrhyncha , in the superfamily Cicadoidea, with large eyes wide apart on the head and usually transparent, well-veined wings. There are about 2,500 species of cicada around the world, and many of them remain unclassified...
s of the genus
MagicicadaMagicicada is the genus of the 13- and 17-year periodical cicadas of eastern North America. They are sometimes called "17-year locusts", although cicadas belong to order Hemiptera, while locusts are Orthoptera....
. These insects spend most of their lives as
grubsA larva is a distinct juvenile form many animals undergo before metamorphosis into adults. Animals with indirect development such as insects, amphibians, or cnidarians typically have a larval phase of their life cycle...
underground. 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 make it very difficult for predators to evolve that could specialize as predators on
Magicicadas. 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. 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.
Generalizations
The concept of prime number is so important that it has been generalized in different ways in various branches of mathematics. Generally, "prime" indicates minimality or indecomposability, in an appropriate sense. For example, the prime field is the smallest subfield of a field
F containing both 0 and 1. It is either
Q or the
finite fieldIn abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
with
p elements, whence the name. Often a second, additional meaning is intended by using the word prime, namely that any object can be, essentially uniquely, decomposed into its prime components. For example, in
knot theoryIn topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life in shoelaces and rope, a mathematician's knot differs in that the ends are joined together so that it cannot be undone. In precise mathematical language, a knot is an embedding of a...
, a
prime knotIn knot theory, a prime knot is a knot that is, in a certain sense, indecomposable. Specifically, it is a non-trivial knot which cannot be written as the knot sum of two non-trivial knots. Knots that are not prime are said to be composite. It can be a nontrivial problem to determine whether a...
is a
knotIn mathematics, a knot is an embedding of a circle in 3-dimensional Euclidean space, R3, considered up to continuous deformations . A crucial difference between the standard mathematical and conventional notions of a knot is that mathematical knots are closed—there are no ends to tie or untie on a...
that is indecomposable in the sense that it cannot be written as the knot sum of two nontrivial knots. Any knot can be uniquely expressed as a connected sum of prime knots.
Prime modelIn mathematics, and in particular model theory, a prime model is a model which is as simple as possible. Specifically, a model P is prime if it admits an elementary embedding into any model M to which it is elementarily equivalent .- Cardinality :In contrast with the notion of saturated model,...
s and prime 3-manifolds are other examples of this type.
Prime elements in rings
{{Main|Prime element|Irreducible element}}
Prime numbers give rise to two more general concepts that apply to elements of any
commutative ringIn ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra....
R, an
algebraic structureIn abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
where addition, subtraction and multiplication are defined:
prime elements and
irreducible elements. An element
p of
R is called prime element if it is neither zero nor a
unitIn mathematics, an invertible element or a unit in a ring R refers to any element u that has an inverse element in the multiplicative monoid of R, i.e. such element v that...
(i.e., does not have a
multiplicative inverseIn mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity, 1. The multiplicative inverse of a fraction a/b is b/a. For the multiplicative inverse of a real number, divide 1 by the...
) and satisfies the following requirement: given
x and
y in
R such that
p divides the product
xy, then
p divides
x or
y. An element is irreducible if it cannot be written as a product of two ring elements that are not units. In the ring
Z of integers, the set of prime elements equals the set of irreducible elements, which is
In any ring
R, any prime element is irreducible. The converse does not hold in general, but does hold for
unique factorization domainIn mathematics, a unique factorization domain is, roughly speaking, a commutative ring in which every element, with special exceptions, can be uniquely written as a product of prime elements , analogous to the fundamental theorem of arithmetic for the integers...
s.
The fundamental theorem of arithmetic continues to hold in unique factorization domains. An example of such a domain is the
Gaussian integerIn number theory, 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 numbers, form an integral domain, usually written as Z[i]. The Gaussian integers are a special case of the quadratic...
s
Z[
i], that is, the set of complex numbers of the form
a +
bi where
i denotes the
imaginary unitIn mathematics, the imaginary unit allows the real number system ℝ to be extended to the complex number system ℂ, which in turn provides at least one root for every polynomial . The imaginary unit is denoted by , , or the Greek...
and
a and
b are arbitrary integers. Its prime elements are known as Gaussian primes. Not every prime (in
Z) is a Gaussian prime: in the bigger ring
Z[
i], 2 factors into the product of the two Gaussian primes (1 +
i) and (1 −
i). Rational primes (i.e. prime elements in
Z) of the form 4
k + 3 are Gaussian primes, whereas rational primes of the form 4
k + 1 are not.
Prime ideals
{{Main|Prime ideals}}
In
ring theoryIn abstract algebra, ring theory is the study of rings—algebraic structures in which addition and multiplication are defined and have similar properties to those familiar from the integers...
, the notion of number is generally replaced with that of
idealIn ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. The ideal concept allows the generalization in an appropriate way of some important properties of integers like "even number" or "multiple of 3"....
.
Prime ideals, which generalize prime elements in the sense that the
principal idealIn ring theory, a branch of abstract algebra, a principal ideal is an ideal I in a ring R that is generated by a single element a of R.More specifically:...
generated by a prime element is a prime ideal, are an important tool and object of study in
commutative algebraCommutative algebra is the branch of abstract algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra...
,
algebraic number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
and
algebraic geometryAlgebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...
. The prime ideals of the ring of integers are the ideals (0), (2), (3), (5), (7), (11), … The fundamental theorem of arithmetic generalizes to the
Lasker–Noether theoremIn mathematics, the Lasker–Noether theorem states that every Noetherian ring is a Lasker ring, which means that every ideal can be written as an intersection of finitely many primary ideals...
, which expresses every ideal in a
NoetherianIn mathematics, more specifically in the area of modern algebra known as ring theory, a Noetherian ring, named after Emmy Noether, is a ring in which every non-empty set of ideals has a maximal element...
commutative ringIn ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra....
as an intersection of
primary idealIn mathematics, specifically commutative algebra, a proper ideal Q of a commutative ring A is said to be primary if whenever xy is an element of Q then x or yn is also an element of Q, for some n...
s, which are the appropriate generalizations of
prime powerIn mathematics, a prime power is a positive integer power of a prime number.For example: 5=51, 9=32 and 16=24 are prime powers, while6=2×3, 15=3×5 and 36=62=22×32 are not...
s.
Prime ideals are the points of algebro-geometric objects, via the notion of the
spectrum of a ringIn abstract algebra and algebraic geometry, the spectrum of a commutative ring R, denoted by Spec, is the set of all proper prime ideals of R...
. Arithmetic geometry also benefits from this notion, and many concepts exist in both geometry and number theory. For example, factorization or
ramificationIn mathematics, the interplay between the Galois group G of a Galois extension L of a number field K, and the way the prime ideals P of the ring of integers OK factorise as products of prime ideals of OL, provides one of the richest parts of algebraic number theory...
of prime ideals when lifted to an
extension fieldIn abstract algebra, field extensions are the main object of study in field theory. The general idea is to start with a base field and construct in some manner a larger field which contains the base field and satisfies additional properties...
, a basic problem of algebraic number theory, bears some resemblance with ramification in geometry. Such ramification questions occur even in number-theoretic questions solely concerned with integers. For example, prime ideals in the
ring of integersIn mathematics, the ring of integers is the set of integers making an algebraic structure Z with the operations of integer addition, negation, and multiplication...
of quadratic number fields can be used in proving
quadratic reciprocityIn number theory, the law of quadratic reciprocity is a theorem about modular arithmetic which gives conditions for the solvability of quadratic equations modulo prime numbers...
, a statement that concerns the solvability of quadratic equations
where
x is an integer and
p and
q are (usual) prime numbers. Early attempts to prove
Fermat's Last TheoremIn number theory, Fermat's Last Theorem states that no three positive integers a, b, and c can satisfy the equation an + bn = cn for any integer value of n greater than two....
climaxed when
KummerKummer may refer to: , German doctor , German , German painter , German fluetist, composer , Austrian female TV presenter , German actor, playwright , Austrian singer...
introduced
regular primes, primes satisfying a certain requirement concerning the failure of unique factorization in the ring consisting of expressions
where
a0, ...,
ap−1 are integers and ζ is a complex number such that
{{nowrapIn mathematics, a root of unity, or de Moivre number, is any complex number that equals 1 when raised to some integer power n. Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, field theory, and the discrete...
.
Valuations
Valuation theory studies certain functions from a field
K to the real numbers
R called valuations. Every such valuation yields a topology on
K, and two valuations are called equivalent if they yield the same topology. A
prime of K (sometimes called a
place of K) is an
equivalence class of valuations. For example, the
p-adic valuationIn number theory, for a given prime number p, the p-adic order or additive p-adic valuation of a number n is the highest exponent ν such that pν divides n. It is commonly abbreviated νp. The most important application of the p-adic order is in constructing the field of p-adic numbers...
of a rational number
q is defined to be the integer
vp(
q), such that
where both
r and
s are not divisible by
p. For example, {{nowrap|
v3(18/7) {{=}} 2.}} The
p-adic norm is defined as
[Some sources also put ]
.
In particular, this norm gets smaller when a number is multiplied by
p, in sharp contrast to the usual
absolute valueIn mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...
(also referred to as the infinite prime). While
completingIn abstract algebra, a completion is any of several related functors on rings and modules that result in complete topological rings and modules. Completion is similar to localization, and together they are among the most basic tools in analysing commutative rings. Complete commutative rings have...
Q (roughly, filling the gaps) with respect to the absolute value yields the
fieldIn abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
of real numbers, completing with respect to the
p-adic norm |−|
p yields the field of
p-adic numbersIn mathematics, and chiefly number theory, the p-adic number system for any prime number p extends the ordinary arithmetic of the rational numbers in a way different from the extension of the rational number system to the real and complex number systems...
. These are essentially all possible ways to complete
Q, by
Ostrowski's theoremOstrowski's theorem, due to Alexander Ostrowski , states that any non-trivial absolute value on the rational numbers Q is equivalent to either the usual real absolute value or a p-adic absolute value.- Definitions :...
. Certain arithmetic questions related to
Q or more general
global fieldIn mathematics, the term global field refers to either of the following:*an algebraic number field, i.e., a finite extension of Q, or*a global function field, i.e., the function field of an algebraic curve over a finite field, equivalently, a finite extension of Fq, the field of rational functions...
s may be transferred back and forth to the completed (or
localIn mathematics, a local field is a special type of field that is a locally compact topological field with respect to a non-discrete topology.Given such a field, an absolute value can be defined on it. There are two basic types of local field: those in which the absolute value is archimedean and...
) fields. This local-global principle again underlines the importance of primes to number theory.
In the arts and literature
Prime numbers have influenced many artists and writers. The French
composerA composer is a person who creates music, either by musical notation or oral tradition, for interpretation and performance, or through direct manipulation of sonic material through electronic media...
Olivier MessiaenOlivier Messiaen was a French composer, organist and ornithologist, one of the major composers of the 20th century. His music is rhythmically complex ; harmonically and melodically it is based on modes of limited transposition, which he abstracted from his early compositions and improvisations...
used prime numbers to create ametrical music through "natural phenomena". In works such as
La Nativité du SeigneurLa Nativité du Seigneur is a work for organ, written by the French composer Olivier Messiaen in 1935....
(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".
In his science fiction novel
ContactContact is a science fiction novel written by Carl Sagan and published in 1985. It deals with the theme of contact between humanity and a more technologically advanced, extraterrestrial life form. It ranked No. 7 on the 1985 U.S. bestseller list....
,
NASAThe National Aeronautics and Space Administration is the agency of the United States government that is responsible for the nation's civilian space program and for aeronautics and aerospace research...
scientist
Carl SaganCarl Edward Sagan was an American astronomer, astrophysicist, cosmologist, author, science popularizer and science communicator in astronomy and natural sciences. He published more than 600 scientific papers and articles and was author, co-author or editor of more than 20 books...
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 DrakeFrank Donald Drake PhD is an American astronomer and astrophysicist. He is most notable as one of the pioneers in the search for extraterrestrial intelligence, including the founding of SETI, mounting the first observational attempts at detecting extraterrestrial communications in 1961 in Project...
in 1975.
Many films, such as
CubeCube is a 1997 Canadian science fiction psychological thriller/horror film directed by Vincenzo Natali. The film was a successful product of the Canadian Film Centre's First Feature Project....
,
SneakersSneakers is a 1992 caper film directed by Phil Alden Robinson, written by Robinson, Walter F. Parkes, and Lawrence Lasker and starring Robert Redford, Dan Aykroyd, Ben Kingsley, Mary McDonnell, River Phoenix, Sidney Poitier and David Strathairn...
,
The Mirror Has Two FacesThe Mirror Has Two Faces is a 1996 American romance film produced and directed by Barbra Streisand, who also stars. The screenplay by Richard LaGravenese is based on the 1958 French film Le Miroir à deux faces written by André Cayatte and Gérard Oury, which focused on a homely woman who becomes a...
and
A Beautiful MindA Beautiful Mind is a 2001 American drama film based on the life of John Nash, a Nobel Laureate in Economics. The film was directed by Ron Howard and written by Akiva Goldsman. It was inspired by a bestselling, Pulitzer Prize-nominated 1998 book of the same name by Sylvia Nasar...
reflect a popular fascination with the mysteries of prime numbers and cryptography. Prime numbers are used as a metaphor for loneliness and isolation in the
Paolo GiordanoPaolo Giordano is an Italian writer who won the Premio Strega literary award with his first novel The Solitude of Prime Numbers.- Biography :...
novel
The Solitude of Prime NumbersThe Solitude of Prime Numbers is a 2010 Italian drama film based on the novel of the same name by Paolo Giordano, and directed by Saverio Costanzo...
, in which they are portrayed as "outsiders" among integers.
External links
{{Wikinews|Two largest known prime numbers discovered just two weeks apart, one qualifies for $100k prize}}
Prime number generators and calculators
{{Divisor classes navbox}}