Prime number

# Prime number

Overview
A prime number is a natural number
Natural number
In 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 divisor
Divisor
In 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 number
Composite number
A 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 arithmetic
Fundamental theorem of arithmetic
In 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 theory
Number theory
Number 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 to
Up to
In 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.
Discussion

Recent Discussions
Encyclopedia
A prime number is a natural number
Natural number
In 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 divisor
Divisor
In 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 number
Composite number
A 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 arithmetic
Fundamental theorem of arithmetic
In 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 theory
Number theory
Number 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 to
Up to
In 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 division
Trial division
Trial 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 prime
Mersenne prime
In 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 digits
Numerical digit
A 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 Euclid
Euclid's theorem
Euclid'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 theorem
Prime number theorem
In 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 probability
Probability
Probability 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 proportional
Proportionality (mathematics)
In 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 logarithm
Logarithm
The 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 conjecture
Goldbach's conjecture
Goldbach'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 prime
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...

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 analytic
Analytic number theory
In 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 algebraic
Algebraic number theory
Algebraic 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 technology
Information technology
Information 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 cryptography
Public-key cryptography
Public-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 algebra
Algebra
Algebra 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 element
Prime element
In 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 ideal
Prime ideal
In 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 number
Natural number
In 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 divisor
Divisor
In 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 composite
Composite number
A 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 remainder
Remainder
In 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 decimal
Decimal
The 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 theory
Number theory
Number 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 unique
Uniqueness quantification
In mathematics and logic, the phrase "there is one and only one" is used to indicate that exactly one object with a certain property exists. In 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 factors
Divisor
In 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 factorization
Integer factorization
In 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 lemma
Euclid's lemma
In 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 Lehmer
Derrick Norman Lehmer
Derrick 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 Lebesgue
Henri Lebesgue
Henri 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 function
Euler's totient function
In 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 Egypt
Ancient Egypt
Ancient 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 Greeks
Ancient Greece
Ancient 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 Elements
Euclid's Elements
Euclid'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 primes
Euclid's theorem
Euclid'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 arithmetic
Fundamental theorem of arithmetic
In 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 number
Perfect number
In 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 prime
Mersenne prime
In 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 Fermat
Pierre de Fermat
Pierre 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 theorem
Fermat's little theorem
Fermat'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 Euler
Leonhard Euler
Leonhard 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 22n + 1 are prime (they are called Fermat numbers) and he verified this up to n = 4 (or 216 + 1). However, the very next Fermat number 232 + 1 is composite (one of its prime factors is 641), as Euler discovered later, and in fact no further Fermat numbers are known to be prime. The French monk Marin Mersenne
Marin Mersenne
Marin 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 2p − 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 number
Natural number
In 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 divisor
Divisor
In 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 number
Composite number
A 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 arithmetic
Fundamental theorem of arithmetic
In 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 theory
Number theory
Number 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 to
Up to
In 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 division
Trial division
Trial 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 prime
Mersenne prime
In 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 digits
Numerical digit
A 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 Euclid
Euclid's theorem
Euclid'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 theorem
Prime number theorem
In 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 probability
Probability
Probability 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 proportional
Proportionality (mathematics)
In 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 logarithm
Logarithm
The 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 conjecture
Goldbach's conjecture
Goldbach'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 prime
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...

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 analytic
Analytic number theory
In 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 algebraic
Algebraic number theory
Algebraic 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 technology
Information technology
Information 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 cryptography
Public-key cryptography
Public-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 algebra
Algebra
Algebra 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 element
Prime element
In 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 ideal
Prime ideal
In 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 number
Natural number
In 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 divisor
Divisor
In 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 composite
Composite number
A 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 remainder
Remainder
In 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 decimal
Decimal
The 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 theory
Number theory
Number 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 unique
Uniqueness quantification
In mathematics and logic, the phrase "there is one and only one" is used to indicate that exactly one object with a certain property exists. In 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 factors
Divisor
In 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 factorization
Integer factorization
In 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 lemma
Euclid's lemma
In 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 Lehmer
Derrick Norman Lehmer
Derrick 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 Lebesgue
Henri Lebesgue
Henri 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 function
Euler's totient function
In 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 Egypt
Ancient Egypt
Ancient 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 Greeks
Ancient Greece
Ancient 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 Elements
Euclid's Elements
Euclid'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 primes
Euclid's theorem
Euclid'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 arithmetic
Fundamental theorem of arithmetic
In 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 number
Perfect number
In 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 prime
Mersenne prime
In 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 Fermat
Pierre de Fermat
Pierre 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 theorem
Fermat's little theorem
Fermat'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 Euler
Leonhard Euler
Leonhard 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 22n + 1 are prime (they are called Fermat numbers) and he verified this up to n = 4 (or 216 + 1). However, the very next Fermat number 232 + 1 is composite (one of its prime factors is 641), as Euler discovered later, and in fact no further Fermat numbers are known to be prime. The French monk Marin Mersenne
Marin Mersenne
Marin 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 2p − 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 number
Natural number
In 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 divisor
Divisor
In 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 number
Composite number
A 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 arithmetic
Fundamental theorem of arithmetic
In 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 theory
Number theory
Number 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 to
Up to
In 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 division
Trial division
Trial 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 prime
Mersenne prime
In 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 digits
Numerical digit
A 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 Euclid
Euclid's theorem
Euclid'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 theorem
Prime number theorem
In 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 probability
Probability
Probability 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 proportional
Proportionality (mathematics)
In 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 logarithm
Logarithm
The 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 conjecture
Goldbach's conjecture
Goldbach'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 prime
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...

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 analytic
Analytic number theory
In 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 algebraic
Algebraic number theory
Algebraic 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 technology
Information technology
Information 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 cryptography
Public-key cryptography
Public-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 algebra
Algebra
Algebra 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 element
Prime element
In 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 ideal
Prime ideal
In 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 number
Natural number
In 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 divisor
Divisor
In 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 composite
Composite number
A 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 remainder
Remainder
In 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 decimal
Decimal
The 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 theory
Number theory
Number 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 unique
Uniqueness quantification
In mathematics and logic, the phrase "there is one and only one" is used to indicate that exactly one object with a certain property exists. In 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 factors
Divisor
In 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 factorization
Integer factorization
In 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 lemma
Euclid's lemma
In 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 Lehmer
Derrick Norman Lehmer
Derrick 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 Lebesgue
Henri Lebesgue
Henri 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 function
Euler's totient function
In 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 Egypt
Ancient Egypt
Ancient 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 Greeks
Ancient Greece
Ancient 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 Elements
Euclid's Elements
Euclid'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 primes
Euclid's theorem
Euclid'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 arithmetic
Fundamental theorem of arithmetic
In 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 number
Perfect number
In 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 prime
Mersenne prime
In 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 Fermat
Pierre de Fermat
Pierre 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 theorem
Fermat's little theorem
Fermat'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 Euler
Leonhard Euler
Leonhard 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 22n + 1 are prime (they are called Fermat numbers) and he verified this up to n = 4 (or 216 + 1). However, the very next Fermat number 232 + 1 is composite (one of its prime factors is 641), as Euler discovered later, and in fact no further Fermat numbers are known to be prime. The French monk Marin Mersenne
Marin Mersenne
Marin 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 2p − 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 divergent
Divergent series
In 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 2p−1(2p − 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 asymptotic
Asymptote
In 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 logarithm
Natural logarithm
The 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
On the Number of Primes Less Than a Given Magnitude
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 Hadamard
Jacques 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 theorem
Prime number theorem
In 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 test
Primality test
A 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 test
Pépin's test
In 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 theorem
Proth's theorem
In 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, ECPP
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...

, and AKS
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"...

work on arbitrary numbers but remain much slower.

For a long time, prime numbers were thought to have extremely limited application outside of pure mathematics
Pure mathematics
Broadly 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 cryptography
Public-key cryptography
Public-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 prime
Largest known prime
The 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 computer
Computer
A 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 Search
Great Internet Mersenne Prime Search
The 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 computing
Distributed computing
Distributed 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 Euclid
Euclid
Euclid , 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 analytical
Mathematical analysis
Mathematical 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's
Christian Goldbach
Christian 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 topology
Furstenberg's proof of the infinitude of primes
In 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's
Ernst Kummer
Ernst 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 number
Euclid number
In 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 reciprocals
Multiplicative inverse
In 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 number
Real number
In 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 theorem
Mertens' theorems
In 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 theorem
Brun's theorem
In 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 prime
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,

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 factorization
Integer factorization
In 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 division
Trial division
Trial 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 root
Square root
In 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 {{=}} 1020}}, 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 sieve
Sieve theory
Sieve 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 Eratosthenes
Sieve of Eratosthenes
In 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 Atkin
Sieve of Atkin
In 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 107 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 algorithm
Deterministic algorithm
In 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 prime
Probable prime
In 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 pseudoprime
Pseudoprime
In 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 theorem
Fermat's little theorem
Fermat'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 proving
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...

. Analyzing its run time is based on heuristic argument
Heuristic argument
A 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 proven
Mathematical proof
In 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 test
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"...

. 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 logarithm
Logarithm
The 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 notation
Big O notation
In 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 log5+ε(n).
Test Developed in Type Running time Notes
AKS primality test
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
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 4k
Solovay–Strassen primality test 1977 probabilistic O(k · log3 n) error probability 2k
Fermat primality test
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!
Factorial
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 prime
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 :...

s. Other primes where either p + 1 or p − 1 is of a particular shape include the Sophie Germain prime
Sophie Germain prime
In 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 2p + 1 with p prime), primorial prime
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....

s, Fermat primes and Mersenne prime
Mersenne prime
In 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|2p − 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 prime
Largest known prime
The 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 {{=}} 22k + 1}}, with k an arbitrary natural number. They are named after Pierre de Fermat
Pierre de Fermat
Pierre 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, 257
257
Year 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-gon
Regular polygon
A regular polygon is a polygon that is equiangular and equilateral . Regular polygons may be convex or star.-General properties:...

is constructible using straightedge and compass
Constructible polygon
In 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 computing
Distributed computing
Distributed 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 Search
Great Internet Mersenne Prime Search
The 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...

### Prime number generators and calculators

{{Divisor classes navbox}}