Lecture
Prime number — a natural (positive integer) number that has exactly two distinct natural divisors — one and itself . In other words, the number 
is prime if it is greater than 
and is divisible without remainder only by and by . For example, 
— is a prime number, while 
is not a prime number, since, besides and , it is also divisible by 
and by 
.
The fundamental theorem of arithmetic establishes the central role of prime numbers in number theory: any integer greater than , either is prime or can be expressed as a product of prime numbers, and this expression is unique up to the order of the factors. It is precisely to ensure uniqueness in this theorem that one is not considered a prime number (otherwise one could include arbitrarily many ones in any factorization , for example, 
and so on).
Natural numbers that are greater than one and are not prime are called composite. Thus, all natural numbers fall into three classes: one (which has one natural divisor), prime numbers (which have two natural divisors), and composite numbers (which have more than two natural divisors) . The study of the properties of prime numbers is the subject of number theory. There are infinitely many prime numbers as well as composite numbers.
The sequence of prime numbers begins as follows:
The property of a number being prime is called primality. A simple but slow method of testing the primality of a given number n is known as trial division; more efficient algorithms are described below.
Factorization of the number 42 into prime factors: 
Many problems concerning prime numbers remain open, see below.
Prime numbers are widely used in mathematics and in related sciences — for example, in many algorithms of information technology, such as public-key cryptosystems, which use properties such as the difficulty of factoring numbers into prime factors .
There are generalizations of the concept of a prime number for arbitrary rings and other algebraic structures, see below.
It is not known when the concept of a prime number was first defined, but the earliest evidence of an understanding of such numbers dates back to the Upper Paleolithic, as confirmed by the Ishango bone .
In the surviving records of the ancient Egyptians there are hints that they had some knowledge of prime numbers: for example, the Rhind papyrus, dating to the 2nd millennium BC, contains a table expressing fractions of the form 2/n as a sum of two, three, or four fractions with numerators equal to one and different denominators. Expansions of fractions whose denominators share a common divisor are similar, which suggests that the Egyptians at least knew the difference between a prime number and a composite one .
However, the earliest surviving studies of prime numbers come from the ancient Greeks. Euclid's Elements (around 300 BC) contain important theorems about prime numbers, including the infinitude of primes, Euclid's lemma, and the fundamental theorem of arithmetic . In ancient Greece the sieve of Eratosthenes was also devised, a simple algorithm for finding all prime numbers from 1 to n.
After the Greeks, little happened in the study of prime numbers until the 17th century . In 1640 Pierre de Fermat formulated (without proof) Fermat's little theorem (later proved by Leibniz and Euler) and the theorem on the sum of two squares. Fermat also conjectured that all numbers of the form 
+ 1 — are prime (they were called Fermat numbers) and proved this up to n = 4 (or 
+ 1). However, Euler showed that the very next Fermat number, for n = 5 (or 
+ 1), is composite (divisible by the number 641). To this day, no other known Fermat numbers are prime. At the same time, the French monk Marin Mersenne drew attention to prime numbers of the form 2p — 1, where p — is prime (not all numbers of this form are prime) . They were named Mersenne primes in his honor.
Euler's work in number theory included a great deal of information about prime numbers. He showed that the infinite series 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + … is divergent. Also, in 1747 he showed that even perfect numbers are integers of the form 
, where the second factor is a Mersenne prime. In correspondence between Euler and Christian Goldbach, the latter formulated the famous Goldbach conjecture about representing any even number, starting from 4, as the sum of two primes, which remains unproven to this day[10].
From the beginning of the 19th century, the attention of many mathematicians turned to the study of the asymptotic distribution of prime numbers[10]. Legendre and Gauss, independently of each other, conjectured that the density of prime numbers on average is close to a value inversely proportional to the natural logarithm[11].
For a long time it was thought that prime numbers had limited application outside of pure mathematics. The situation changed in the 1970s, when the concepts of public-key cryptography appeared; in them prime numbers formed the basis of the first algorithms, such as the RSA encryption algorithm[12].
The representation of a natural number as a product of primes is called decomposition into primes or factorization of the number. At present no polynomial-time algorithms for factoring numbers are known, although it has not been proven that such algorithms do not exist. The RSA cryptosystem and several others are based on the presumed high computational complexity of the factorization problem. Factorization with polynomial complexity is theoretically possible on a quantum computer using Shor's algorithm[13].
The fundamental theorem of arithmetic states that every natural number greater than one can be represented as a product of prime numbers, and in a unique way up to the order of the factors[14]. Thus, prime numbers are the elementary «building blocks» of natural numbers. For example:
 |
 |
 . ( denotes the square, or second power, of .) |
As shown in this example, the same prime divisor can appear several times. The decomposition:
n = p1 · p2 · ... · pt
of a number n into (a finite number of) prime factors p1, p2, … ,pt is called the decomposition into prime factors of the number n. The fundamental theorem of arithmetic can be rephrased as follows: any decomposition into prime numbers will be identical up to the order of the divisors. In practice, for most numbers there are many simple algorithms for factoring into factors, all of which give the same result[13].
Most ancient Greeks did not even consider to be a number, so they could not consider it prime[15]. By the Middle Ages and the Renaissance, many mathematicians included as the first prime number[16]. In the middle of the 18th century, Christian Goldbach added to the list as the first prime number in his famous correspondence with Leonhard Euler; however, Euler himself did not consider to be a prime number[17]. In the 19th century, many mathematicians still considered the number to be prime. For example, the list of prime digits by Derrick Norman Lehmer up to 
, reprinted in 1956, began with as the first prime number. Henri Lebesgue is said to be the last mathematician to have called prime[18]. By the early 20th century, mathematicians began to reach a consensus that is not a prime number, but rather forms its own special category — a «unit»[16].
If is considered a prime number, then the fundamental theorem of arithmetic of Euclid (mentioned above) would not hold as stated. For example, the number 
could be factored as 3 · 5 and 1 · 3 · 5. If were a prime number, these two variants would be considered different factorizations of , and consequently the statement of this theorem would have to be changed[16]. In the same way, the sieve of Eratosthenes would work incorrectly if were considered prime: the modified version of the sieve, which assumes that is a prime number, excludes all multiples of (that is, all other numbers) and yields as output only a single number — . Moreover, prime numbers have several properties that the number does not, such as the relationship of a number to its corresponding value of Euler's totient function or the sum-of-divisors function .
Simple ways of finding an initial list of prime numbers up to a certain value are given by the sieve of Eratosthenes, the sieve of Sundaram, and the sieve of Atkin[19].
In practice, however, instead of obtaining a list of prime numbers, it is often necessary to check whether a given number is prime. Algorithms that solve this problem are called primality tests. There are many polynomial primality tests, but most of them are probabilistic (for example, the Miller–Rabin test) and are used for the needs of cryptography[20]. In 2002 it was proven that the problem of primality testing is, in general, solvable in polynomial time, but the proposed deterministic Agrawal–Kayal–Saxena test has a fairly high computational complexity, which makes its practical application difficult[21].
For some classes of numbers there exist specialized efficient primality tests (see below).
A primality test (or a primality check) is an algorithm which, given a number as input, allows one to either fail to confirm the assumption that the number is composite, or to assert its primality with certainty. In the second case it is called a true primality test. The problem of primality testing belongs to complexity class P, that is, the running time of algorithms solving it depends polynomially on the size of the input data, as was proven in 2002[22]. The appearance of a polynomial algorithm was predicted by the existence of polynomial primality certificates and, as a consequence, by the fact that the problem of checking a number for primality belonged to the classes NP and co-NP simultaneously.
Existing algorithms for checking a number for primality can be divided into two categories: true primality tests and probabilistic primality tests. The result of computations of true tests is always the fact of primality or compositeness of the number. A probabilistic test shows whether a number is prime with a certain probability. Numbers that satisfy a probabilistic primality test but are composite are called pseudoprimes[23]. One example of such numbers are Carmichael numbers[24].
One example of true primality tests is the Lucas–Lehmer test for Mersenne numbers. An obvious drawback of this test is that it is applicable only to numbers of a certain form. Among other examples we can cite those based on Fermat's little theorem[25]
As well as:
Probabilistic primality tests include:
For many centuries now the search for «large» prime numbers has aroused the interest of mathematicians. In recent decades, this research has acquired practical significance because of the use of such numbers in a number of encryption algorithms, such as RSA[12].
In the seventeenth century, Marin Mersenne conjectured that numbers of the form 
are prime (for n ≤ 257) only for n equal to 2, 3, 5, 7, 13, 19, 31, 67, 127, and 257.[11] Verifying the truth of the conjecture was far beyond the capabilities of that time. Only in the 20th century was it discovered that the hypothesis was false and had probably been made «blindly», since Mersenne had failed to account for three cases (for n = 61, 89, and 107); moreover, it turned out that the numbers corresponding to n = 67 and n = 257 are composite[11].
In 1876, Édouard Lucas proved that the number M 127 (a 39-digit number) is prime; it remained the largest known prime number until 1951, when 
(44 digits) was found, and, slightly later, 
(of 79 digits) — the last prime number to be found using an electronic calculator. Since then, all subsequent large prime numbers have been found using a computer: from 1952 (when SWAC showed that M 521 is prime) to 1996 they were found by a supercomputer, and all were Mersenne primes (found using the Lucas–Lehmer test, an algorithm specific to such numbers), with the exception of the number 
, which was the record between 1989 and 1992[27].
Some problems in mathematics involving factorization require a number of very large prime numbers, chosen at random. The algorithm for obtaining them, based on Bertrand's postulate (For any natural n ≥ 2 there exists a prime number p in the interval n < p < 2n.)[28]:
The time to solve the problem with this algorithm is not determined, but there is a strong likelihood that it is always polynomial, as long as there are enough prime numbers and they are distributed more or less uniformly. For random prime numbers these conditions are satisfied[21].
The most effective means of constructing prime numbers is a somewhat modified version of Fermat's little theorem[26].
Let N, S be odd natural numbers, N-1 = S*R, and suppose that for every prime divisor q of the number S there exists an integer 
such that
, 
Then every prime divisor p of the number N satisfies the congruence
Corollary. If the conditions of Fermat's theorem hold and 
, then N is a prime number.[26]
Let us now show how, using the last statement, having a large prime number 
, one can construct a substantially larger prime number 
. For this, let us choose at random an even number 
in the interval and set 
. Then let us check the number for the absence of small prime divisors, dividing it by small prime numbers; let us test a certain number of times using the Rabin algorithm. If it then turns out that is a composite number, a new value of should be chosen and the computations repeated again. This should be done until a number N is found that has withstood the Rabin algorithm's test a sufficient number of times. In this case there arises a hope that is a prime number, and one should attempt to prove primality using primality tests[26].
There are infinitely many prime numbers. This statement is referred to as Euclid's theorem in honor of the ancient Greek mathematician Euclid, since the first known proof of this statement is attributed to him. Many other proofs of the infinitude of prime numbers are known, including Euler's analytic proof, Goldbach's proof based on Fermat numbers[29], Furstenberg's proof using general topology, and Kummer's elegant proof.
Records noting the largest prime numbers known at a given time have long been kept[30]. One of the records was set in his time by Euler, who found the prime number 231 − 1 = 2,147,483,647.
The largest known prime number, as of January 2019, is the Mersenne number M82,589,933 = 282,589,933 − 1. It contains 24,862,048 decimal digits; a book recording this number would run to about nine thousand pages. It was found on December 7, 2018 as part of the GIMPS distributed computing project for searching for Mersenne prime numbers. The previous largest known prime number, discovered in December 2017, was 1,612,623 digits smaller[31].
Mersenne numbers have an advantage over other numbers in having an efficient primality test: the Lucas–Lehmer test. Thanks to this, Mersenne prime numbers have long held the record as the largest known primes.
For finding prime numbers of more than 100,000,000 and 1,000,000,000 decimal digits, the EFF has offered[32] cash prizes of 150,000 and 250,000 US dollars respectively[33]. The EFF had previously awarded prizes for finding prime numbers of 1,000,000 and 10,000,000 decimal digits.
There exists a number of numbers whose primality can be established efficiently using specialized algorithms.
, where n is a natural number[34]. Here, a Mersenne number can be prime only if n is a prime number. As already noted above, an efficient primality test is the Lucas–Lehmer test[35].
, where n is a nonnegative integer[36]. An efficient primality test is the Pépin test. As of February 2015, only 5 Fermat prime numbers are known (for n = 0, 1, 2, 3, 4); the next twenty-eight Fermat numbers (up to and including 
) turned out to be composite[37], however it has not been proven that there are no other Fermat prime numbers[38].
[39]. An efficient primality test is the Lucas–Lehmer–Riesel test[40].
[41][42].
, where k is odd and 
[43]. An efficient primality test for Proth numbers is the Brillhart–Lehmer–Selfridge test (Brillhart–Lehmer–Selfridge test)[44]. Cullen numbers and Fermat numbers are a special case of Proth numbers (respectively when k = n and when k = 1, 
)[45].
where 
is the Mills constant[46].To search for prime numbers of the noted types, the distributed computing projects GIMPS, PrimeGrid, Ramsey@Home, Seventeen or Bust, Riesel Sieve, and Wieferich@Home are currently used.
is a field if and only if 
is prime[48].
is prime, and is natural, then 
is divisible by (Fermat's little theorem)[49].
is a finite group whose order 
is divisible by , then contains an element of order (Cauchy's theorem)[50]. is a finite group, and 
is the maximal power of that divides , then has a subgroup of order , called a Sylow subgroup; moreover, the number of Sylow subgroups equals 
for some integer 
(Sylow's theorems)[51].
is prime if and only if 
is divisible by (Wilson's theorem)[52].
is natural, then there exists a prime such that 
(Bertrand's postulate)[53].
, where 
are coprime integers, contains infinitely many prime numbers (Dirichlet's theorem on primes in arithmetic progressions)[54].
or 
, where is some natural number. Hence, if the difference between several consecutive prime numbers (for k>1) is the same, it is necessarily a multiple of 6 — for example: 251-257-263-269; 199-211-223; 20183-20201-20219.
is prime, then 
is a multiple of 24 (also holds for all odd numbers not divisible by 3)[55].
, where n>2, k>1. In other words, the number following a prime cannot be a square or a higher power with a base greater than 2. It also follows from this that if a prime number has the form 
, then k is prime (see Mersenne numbers)[34].
, where n>1, k>0. In other words, the number preceding a prime cannot be a cube or a higher odd power with a base greater than 1[57].Prime numbers are fundamental components in many areas of mathematics.
Arithmetic functions, namely functions defined on the set of natural numbers and taking values in the set of complex numbers, play a decisive role in number theory. In particular, among them the most important are multiplicative functions, that is, functions 
, possessing the following property: if a pair 
consists of coprime numbers, then the equality holds[59]
Examples of multiplicative functions are Euler's function 
, which associates with the number the count of natural numbers less than n and coprime to it, and the number of divisors of the number n[60]. The value of these functions at a power of a prime number:
:
Arithmetic functions can be easily computed once we know the values they take at powers of prime numbers[59]. In fact, from the factorization of a natural number n into factors
we have that
and therefore, returning to the problem of computing 
it turns out that computing at each power of a prime divisor is usually simpler than computing by the general formula.[61]
For example, to find the value of Euler's function at n = 450 = 2 × 3 2 × 5 2, it suffices to compute
In modular arithmetic, prime numbers play a very important role: the ring of residues 
is a field if and only if n is prime.[48] Also, the existence of a primitive root of the ring is tied to prime numbers: it exists only if n is a prime number, 1, 2, 4, or a number of the form 
, where p is odd.
One of the most important theorems of modular arithmetic is Fermat's little theorem[52]. This theorem states that for any prime number p and any natural number a, we have:
or for any prime p and any natural a not divisible by p, the following holds:
This property can be used to check that a number is not prime. In fact, if n is such that:
for some natural a, then n cannot be prime[52]. However, this property cannot be used to test a number for primality: there exist certain numbers called Carmichael numbers (the smallest being 561) for which this fails. A Carmichael number is a composite number that is a pseudoprime to every base b coprime to n. In 1994, William Robert Alford, Andrew Granville, and Carl Pomerance showed that there are infinitely many such numbers[62].
Prime numbers also play a fundamental role in algebra. In group theory, a group in which every element is a power of a prime number p is called a p-group[63]. A p-group is finite if and only if the order of the group (the number of its elements) is a power of p. An example of an infinite p-group is the p-group Prüfer[64]. It is known that p-groups have a nontrivial center and, therefore, cannot be simple (except for the group with p elements); moreover, if the group is finite, all normal subgroups intersect the center nontrivially.
An example of such groups is the cyclic multiplicative group modulo a prime number[65].
All groups of order p are cyclic and therefore abelian; every group of order p 2 is likewise abelian. Moreover, any finite abelian group is isomorphic to a direct product of finitely many cyclic p-groups.
Cauchy's theorem states that if the order of a finite group G is divisible by a prime number p, then G contains elements of order p. This theorem is generalized by the Sylow theorems[50].
Some public-key cryptography algorithms, such as RSA and Diffie-Hellman key exchange, are based on large prime numbers (usually 1024—2048 bits). RSA relies on the assumption that it is much simpler (that is, more efficient) to multiply two (large) numbers x and y, than to compute the coprime x and y, if only their product 
is known. Diffie-Hellman key exchange is based on the fact that there exist efficient algorithms for modular exponentiation, while the inverse operation — discrete logarithm — is considered hard[66][67].
The difficulty of factoring large numbers led to the development of the first efficient public-key cryptography method — RSA.[68] In this cryptographic system, the person who is to receive an encrypted message generates a key: two distinct random prime numbers and 
of a given size are chosen (usually 1024- or 2048-bit numbers are used). Next their product 
, called the modulus, is computed. The value of Euler's function of the number is computed: 
. An integer 
(
) is chosen that is coprime to the value of the function 
. Usually small prime numbers are taken as (for example, Fermat primes). The number is called the public exponent (English: public exponent). The number 
is computed, called the secret exponent, the multiplicative inverse of the number e modulo . The pair 
is published as the RSA public key (English: RSA public key). The pair 
plays the role of the RSA private key (English: RSA private key) and is kept secret[12].
Theoretically, it is possible to obtain the private key from publicly available information: at present this requires the factorization of the number , which makes the transmission of a protected message secure if the prime numbers satisfy certain conditions and are «large enough». It is not yet known whether there exist efficient methods for decrypting the message that are not related to a direct attack on the factorization of , but it has been shown that a poor choice of public key can make the system more vulnerable to such attacks.[69]
In 1991, RSA Security published a list of semiprime numbers, offering cash prizes for factoring some of them, with the aim of confirming the security of the method and encouraging research in this area: the initiative was called the RSA Factoring Challenge.[70] Over the years some of these numbers have been factored, while for others the factorization problem still remains open; however, the contest was concluded in 2007[70].
At various times attempts have been made to specify an expression whose values, for different values of the variables occurring in it, would be prime numbers[54]. L. Euler pointed out the polynomial 
that takes prime values for n = 0, 1, 2, …, 40. However, for n = 41 the value of the polynomial is a composite number. It can be proved that there is no polynomial in a single variable n that takes prime values for all integer n[54]. P. Fermat conjectured that all numbers of the form 22k + 1 are prime; however, Euler disproved this conjecture by showing that the number 225 + 1 = 4,294,967,297 — is composite[54].
Nevertheless, there exist polynomials whose set of positive values, for nonnegative values of the variables, coincides with the set of prime numbers. One example is the polynomial
containing 26 variables and having degree 25. The lowest degree for known polynomials of this type is 5, with 42 variables; the smallest number of variables is 10, with a degree of about 1.6·1045[71][72]. This result is a special case of the diophantineness of every enumerable set, proved by Yuri Matiyasevich.
Interestingly, the polynomial given above, which generates prime numbers, itself factors. Note that the second factor of this polynomial (in curly braces) has the form: one minus the sum of squares. Thus, the polynomial can take positive values (for positive ) only if each of these squares (that is, each polynomial in square brackets) equals zero. In this case the expression in curly braces will equal 1[73].
There are still many open questions concerning prime numbers, the most famous of which were listed by Edmund Landau at the Fifth International Congress of Mathematicians[74]:
there is always a prime number between 
and 
[77]?
, where is a natural number, infinite[54]?An open problem is also the existence of infinitely many prime numbers in many integer sequences, including Mersenne numbers[54], Fibonacci numbers, Fermat numbers, and others.
At the beginning of the article, a prime number was defined: a natural number is called prime if it has exactly two divisors — one and itself. An analogous concept can be introduced in other algebraic structures; most often commutative rings without zero divisors (integral domains) are considered[78][79]. Such rings, however, can have unit divisors forming a multiplicative group. For example, in the ring of integers there exist two unit divisors: 
and 
Therefore all integers, except the unit divisors, have not two but at least four divisors; for example, the divisors of the number 7 are 
This means that a generalization of the concept of a prime number must rely on other properties of it.
The analogue of a prime number for an integral domain is an irreducible element, which is defined as follows[80].
|
A nonzero element |
For integers, this definition means that the irreducible elements are the prime natural numbers, as well as their negatives.
From the definition it follows that the set of divisors of an irreducible element consists of two parts: all unit divisors, and the products of with all unit divisors (these products are called elements associated with ). That is, the number of divisors of an irreducible 
, if it is finite, is twice the number of unit divisors in the ring.
Of great importance is the analogue of the fundamental theorem of arithmetic, which in its generalized form is stated as follows[81]:
|
A ring is called factorial if every nonzero element in it that is not a unit divisor can be represented as a product of irreducible elements, and this representation is unique up to the permutation of the factors and their associativity (multiplication by unit divisors). |
Not every integral domain is factorial, see the counterexample. A Euclidean ring is always factorial[82].
There is another, narrower generalization of the concept of a prime number, called a prime element[80].
|
A nonzero element |
A prime element is always irreducible. Indeed, if the element is prime and 
then by the definition of a prime element one of the factors, let it be 
is divisible by that is, 
Then 
or, cancelling by (in an integral domain cancelling a nonzero factor is always possible): 
that is, 
is a unit divisor. ■
The converse, generally speaking, is not true: an irreducible element may not be prime if the ring is not factorial. Example[83]: consider the ring of numbers of the form 
where 
are integers. The number 3 is irreducible in it, since it has only 4 divisors: 
. However, it is not a prime element, as the following equality shows:
The number 3 divides the right-hand side of the equality, but does not divide either of the factors. From this fact one can conclude that the ring under consideration is not factorial; and indeed, the equality 
shows that the factorization into irreducible factors in this ring is not unique.
The ring of integers is factorial. In it, as already mentioned above, there are two unit divisors.
The ring of Gaussian numbers consists of complex numbers of the form 
where are integers. There are four unit divisors: 
This ring is factorial; the irreducible elements are some of the ordinary prime numbers and the «Gaussian primes» (for example, 
). See the criterion for the primality of a Gaussian number.
An example of a factorization for the number 2, which in the ring of Gaussian numbers is not prime: 
— the non-uniqueness of the factorization here is only apparent, since 
is associated with , according to the equality: 
The ring of Eisenstein integers 
consists of complex numbers of the following form[84]:
where are integers, 
(a cube root of unity),
In this ring there are six unit divisors: (±1, ±ω, ±ω2), it is Euclidean and therefore factorial. The irreducible elements (which are also the prime elements) of the ring are called Eisenstein prime numbers.
Primality criterion: an Eisenstein integer 
is an Eisenstein prime number if and only if one of the following mutually exclusive conditions holds:
is associated with a natural prime number of the form 
(the norm ) is a natural prime of the form 
or 
.It follows that the norm of any Eisenstein integer is either a prime natural number or the square of a prime natural number[84].
Numbers associated with, or complex-conjugate to, Eisenstein prime numbers are also Eisenstein prime numbers.
Of great importance in algebra is the polynomial ring 
, formed by polynomials with coefficients from some ring 
The unit divisors here are the nonzero constants (as polynomials of degree zero). The polynomial ring is Euclidean and therefore factorial. If the field of real numbers is taken as 
, then the irreducible polynomials will be all first-degree polynomials and those second-degree polynomials that have no real roots (that is, their discriminant is negative)[85].
implies that 
can be divisible by 
Comments