Prime number

A prime number, also referred to as a prime, is defined as a natural number exceeding 1 that cannot be expressed as the product of two smaller natural numbers. Conversely, any natural number greater than 1 that is not prime is designated a composite number. For instance, the number 5 is prime because its only multiplicative decompositions, 1 × 5 or 5 × 1, necessarily include 5 itself. In contrast, 4 is classified as composite, as it can be formed by the product (2 × 2) where both factors are less than 4. Prime numbers hold a foundational position in number theory due to the fundamental theorem of arithmetic, which states that every natural number greater than 1 is either a prime number itself or possesses a unique factorization into a product of primes, irrespective of the order of the factors.

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

The characteristic of being prime is termed primality. A straightforward, albeit inefficient, technique for ascertaining the primality of a given number ⁠${\displaystyle n}$⁠ is trial division, which involves checking if ⁠${\displaystyle n}$⁠ is divisible by any integer from 2 up to ⁠${\displaystyle {\sqrt {n}}}$⁠. More rapid algorithms exist, such as the Miller–Rabin primality test, which offers speed at the cost of a minor probability of error, and the AKS primality test, which guarantees a correct result in polynomial time but is generally too slow for practical applications. Specialized and exceptionally fast methods are applicable to numbers with particular structures, exemplified by Mersenne numbers. As of October 2024, the largest identified prime number is a Mersenne prime, possessing 41,024,320 decimal digits.

The infinitude of prime numbers was established by Euclid approximately 300 BC. Currently, no straightforward formula exists to distinguish prime numbers from composite numbers. Nevertheless, the large-scale distribution of primes among natural numbers can be effectively modeled statistically. The seminal achievement in this area is the prime number theorem, proved in the late 19th century, which posits that the probability of a randomly selected large integer being prime is approximately inversely proportional to its number of digits, or equivalently, to its logarithm.

Numerous long-standing questions concerning prime numbers remain unresolved. Notable among these are Goldbach's conjecture, which proposes that every even integer exceeding 2 can be represented as the sum of two primes, and the twin prime conjecture, which postulates the existence of infinitely many prime pairs differing by two. These inquiries have stimulated the evolution of diverse subfields within number theory, emphasizing either the analytic or algebraic properties of numbers. Prime numbers are integral to various information technology protocols, including public-key cryptography, which leverages the computational challenge of factoring large integers into their prime components. Within abstract algebra, concepts analogous to prime numbers, exhibiting generalized prime-like behavior, encompass prime elements and prime ideals.

Definition and Illustrative Examples

A natural number (e.g., 1, 2, 3, 4, 5, 6) is designated a prime number (or simply a prime) if it exceeds 1 and cannot be expressed as the product of two natural numbers, both smaller than itself. Natural numbers greater than 1 that do not satisfy this criterion are termed composite numbers. Alternatively, a number ⁠${\displaystyle n}$⁠ is prime if ⁠${\displaystyle n}$⁠ discrete items cannot be partitioned into smaller, equal-sized groups containing more than one item, or if ⁠${\displaystyle n}$⁠ dots cannot be arranged into a rectangular grid with dimensions greater than one dot in both width and height. For instance, within the sequence of numbers from 1 to 6, 2, 3, and 5 are identified as prime numbers because they are not evenly divisible by any other integers (i.e., without a remainder). The number 1 is not considered prime, as it is explicitly excluded by the definition. Both 4 = 2 × 2 and 6 = 2 × 3 are examples of composite numbers.

The divisors of a natural number ⁠${\displaystyle n}$⁠ are defined as the natural numbers that divide ⁠${\displaystyle n}$⁠ without a remainder. Each natural number possesses at least two divisors: 1 and the number itself. A number is not prime if it has any divisor other than 1 and itself. Consequently, prime numbers are equivalently defined as integers possessing precisely two positive divisors. These two divisors are 1 and the number itself. Since 1 has only one divisor (itself), it is excluded from the set of prime numbers under this definition. Alternatively, a number ⁠${\displaystyle n}$⁠ is considered prime if it exceeds one and is not divisible without remainder by any integer in the sequence §6061§ , §6465§ , …<!-- … --> , n −<!-- − --> §7879§ {\displaystyle 2,3,\dots ,n-1} .

The initial 25 prime numbers, encompassing all primes below 100, are listed as follows:

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 (OEIS sequence A000040).

An even number ⁠${\displaystyle n}$⁠ exceeding 2 cannot be prime, as it can invariably be expressed as the product ⁠§2526§ × n / §3637§ {\displaystyle 2\times n/2} ⁠. Consequently, all prime numbers except 2 are odd and are referred to as odd primes. Furthermore, in the standard decimal system, prime numbers greater than 5 consistently terminate with the digits 1, 3, 7, or 9. Numbers concluding with other digits are composite: those ending in 0, 2, 4, 6, or 8 are even, while those ending in 0 or 5 are divisible by 5.

The collective set of all prime numbers is conventionally represented by the notation ${\displaystyle \mathbf {P} }$ (a boldface capital P) or ${\displaystyle \mathbb {P} }$ (a blackboard bold capital P).

History

Dating to approximately 1550 BC, the Rhind Mathematical Papyrus contains Egyptian fraction expansions that differentiate between prime and composite numbers. Nevertheless, the earliest extant documentation concerning the systematic study of prime numbers originates from ancient Greek mathematicians, who designated them as prōtos arithmòs (πρῶτος ἀριθμὸς). Euclid's seminal work, Elements (circa 300 BC), provides proof for the infinitude of primes, establishes the fundamental theorem of arithmetic, and outlines a method for constructing perfect numbers from Mersenne primes. The Sieve of Eratosthenes, another significant Greek innovation, remains a contemporary method for generating lists of primes.

Around 1000 AD, the Islamic mathematician Ibn al-Haytham (Alhazen) discovered Wilson's theorem, which characterizes prime numbers as those integers ⁠

In 1640, Pierre de Fermat articulated Fermat's Little Theorem, a proposition he presented without formal proof, which was subsequently substantiated by Leibniz and Euler. Fermat additionally conducted research into the primality of Fermat numbers, expressed as ⁠§89§ §1213§ n + §2324§ {\displaystyle 2^{2^{n}}+1} ⁠. Concurrently, Marin Mersenne undertook investigations into Mersenne primes, which are prime numbers characterized by the form §4142§ p − §5152§ {\displaystyle 2^{p}-1} , where ⁠${\displaystyle p}$⁠ is itself a prime number. In a 1742 correspondence with Euler, Christian Goldbach proposed Goldbach's conjecture, positing that every even integer can be expressed as the sum of two prime numbers. Euler subsequently demonstrated the validity of Alhazen's conjecture (presently recognized as the Euclid–Euler theorem), establishing that all even perfect numbers are derivable from Mersenne primes. Furthermore, Euler integrated analytical methods into this domain through his demonstrations of the infinite nature of prime numbers and the divergence of the series comprising the reciprocals of primes, represented as ⁠§8990§ §9192§ + §101102§ §103104§ + §113114§ §115116§ + §125126§ §127128§ + §137138§ §139140§ + ⋯ {\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots } ⁠. Early in the 19th century, Legendre and Gauss independently hypothesized that as ⁠${\displaystyle x}$⁠ approaches infinity, the count of prime numbers less than or equal to ⁠${\displaystyle x}$⁠ is asymptotically equivalent to ⁠${\displaystyle x/\log x}$⁠, with ${\displaystyle \log x}$ denoting the natural logarithm of ⁠${\displaystyle x}$⁠. Bertrand's Postulate, a less stringent implication of this observed high density of prime numbers, asserts that for any integer 273§ {\displaystyle n>1} , a prime number exists strictly between ⁠${\displaystyle n}$⁠ and ⁠§307308§ n {\displaystyle 2n} ⁠, a proposition rigorously established in 1852 by Pafnuty Chebyshev. Bernhard Riemann's 1859 publication concerning the zeta-function presented a conceptual framework for substantiating the conjecture put forth by Legendre and Gauss. While the intimately connected Riemann Hypothesis continues to defy proof, Riemann's foundational framework was ultimately formalized in 1896 by Hadamard and de la Vallée Poussin, culminating in what is now recognized as the Prime Number Theorem. A further significant mathematical achievement of the 19th century was Dirichlet's Theorem on Arithmetic Progressions, which demonstrated that specific arithmetic progressions encompass an infinite quantity of prime numbers.

Numerous mathematicians have developed primality tests for numbers exceeding the practical limits of trial division. Specialized primality tests, applicable to numbers of particular forms, encompass Pépin's test for Fermat numbers (1877), Proth's theorem (c. 1878), the Lucas–Lehmer primality test (originated 1856), and the generalized Lucas primality test.

Since 1951, the largest known prime numbers have been identified through the application of these tests on computers. The ongoing quest for increasingly large primes has attracted broader interest beyond academic mathematics, notably through initiatives like the Great Internet Mersenne Prime Search and other distributed computing projects. The perception that prime numbers held limited utility beyond pure mathematics was fundamentally altered in the 1970s with the advent of public-key cryptography and the RSA cryptosystem, both of which are fundamentally based on prime numbers.

The growing practical significance of computerized primality testing and factorization necessitated the development of advanced methods for processing large numbers of arbitrary form. Concurrently, the mathematical theory of prime numbers advanced significantly with the Green–Tao theorem (2004), demonstrating the existence of arbitrarily long arithmetic progressions of prime numbers, and Yitang Zhang's 2013 proof, establishing the existence of infinitely many prime gaps of bounded magnitude.

The Primality of One

In antiquity, most early Greek mathematicians did not classify 1 as a number, precluding any consideration of its primality. A minority of scholars within the Greek and later Roman traditions, such as Nicomachus, Iamblichus, Boethius, and Cassiodorus, further categorized prime numbers as a subset of odd numbers, consequently excluding ⁠§78§ {\displaystyle 2} ⁠ from primality. Conversely, Euclid and most other Greek mathematicians recognized ⁠§2526§ {\displaystyle 2} ⁠ as a prime number. Medieval Islamic mathematicians generally adopted the Greek perspective, not considering 1 to be a number. During the Middle Ages and Renaissance, mathematicians started to acknowledge 1 as a number, and by the 17th century, some even classified it as the initial prime. In the mid-18th century, Christian Goldbach included 1 in his list of primes during correspondence with Leonhard Euler; however, Euler himself did not regard 1 as prime. Numerous 19th-century mathematicians continued to consider 1 prime, with Derrick Norman Lehmer notably including it in his list of primes less than ten million published in 1914. Lists of primes containing 1 were still published as late as 1956. Nevertheless, by the early 20th century, a consensus emerged among mathematicians that 1 should not be classified as prime, but instead be designated as a unique category, a "unit".

Classifying 1 as a prime number would necessitate cumbersome rephrasing of numerous mathematical statements concerning primes. For instance, the fundamental theorem of arithmetic would require reformulation to specify factorizations into primes greater than 1, as every number would otherwise possess multiple factorizations incorporating an arbitrary quantity of 1s. Likewise, the Sieve of Eratosthenes would malfunction if 1 were treated as a prime, as it would erroneously eliminate all multiples of 1 (i.e., all other integers), yielding only the number 1 itself. Furthermore, several technical properties characteristic of prime numbers do not apply to 1; for example, the formulas for Euler's totient function and the sum of divisors function differ for prime numbers compared to 1.

Elementary Properties

Unique Factorization

The representation of an integer as a product of prime numbers is termed its prime factorization. For instance:

${\displaystyle {\begin{aligned}50&=2\times 5\times 5\\&=2\times 5^{2}.\end{aligned}}}$

The individual components within a product are referred to as prime factors. A particular prime factor can appear multiple times; for instance, in this illustration, the prime factor ${\displaystyle 5.}$ is present twice. When a prime number recurs, exponentiation offers a method to consolidate these repeated instances: for example, in the alternative representation of the product previously mentioned, §2526§ §2829§ {\displaystyle 5^{2}} signifies the square, or second power, of ⁠${\displaystyle 5}$⁠.

The pivotal role of prime numbers in both number theory and broader mathematics originates from the fundamental theorem of arithmetic. This theorem posits that every integer exceeding one can be expressed as a product comprising one or more prime numbers. Furthermore, this factorization is uniquely determined, meaning that any two prime factorizations of an identical number will invariably contain the same multiplicity of each prime, notwithstanding potential variations in their sequence. Consequently, despite the existence of diverse integer factorization algorithms, all methods are guaranteed to yield an identical outcome. Thus, prime numbers are conceptualized as the foundational "basic building blocks" of the natural number system.

Several demonstrations of the uniqueness of prime factorizations rely on Euclid's lemma, which states: If ⁠${\displaystyle p}$⁠ is a prime number and ⁠${\displaystyle p}$⁠ divides the product ${\displaystyle ab}$ of integers ⁠${\displaystyle a}$⁠ and ${\displaystyle b,}$, then ⁠${\displaystyle p}$⁠ must divide ⁠${\displaystyle a}$⁠ or ⁠${\displaystyle p}$⁠ must divide ⁠${\displaystyle b}$⁠ (or both). Conversely, if a number ⁠${\displaystyle p}$⁠ possesses the characteristic that its division of a product invariably results in it dividing at least one factor of that product, then ⁠${\displaystyle p}$⁠ is necessarily prime.

Infinitude

The existence of an infinite number of prime numbers is a fundamental concept in number theory. This implies that the sequence

${\displaystyle 2,3,5,7,11,13,...}$

of prime numbers is unending. This fundamental assertion is known as Euclid's theorem, named after the ancient Greek mathematician Euclid, who is credited with providing the earliest known proof. Numerous subsequent proofs for the infinitude of primes have been developed, notably an analytical proof by Euler, Goldbach's proof derived from Fermat numbers, Furstenberg's proof employing general topology, and Kummer's refined demonstration.

Euclid's proof demonstrates that any finite enumeration of prime numbers is inherently incomplete. The core principle involves multiplying all primes within a specified list and subsequently adding ${\displaystyle 1.}$. For a list comprising the primes p §2627§ , p §3637§ , … , p n , {\displaystyle p_{1},p_{2},\ldots ,p_{n},} , this operation yields the number

N = §1011§ + p §1819§ ⋅ p §2930§ ⋯ p n . {\displaystyle N=1+p_{1}\cdot p_{2}\cdots p_{n}.}

According to the fundamental theorem of arithmetic, ⁠${\displaystyle N}$⁠ possesses a unique prime factorization, expressed as

N = p §1415§ ′ ⋅ p §2728§ ′ ⋯ p m ′ {\displaystyle N=p'_{1}\cdot p'_{2}\cdots p'_{m}}

where ⁠${\displaystyle N}$⁠ possesses one or more prime factors. While ⁠${\displaystyle N}$⁠ is perfectly divisible by each of these newly identified factors, it yields a remainder of one when divided by any prime number from the initial list. Consequently, none of the prime factors of ⁠${\displaystyle N}$⁠ can be members of the original finite list. This logical deduction confirms that no finite list can encompass all prime numbers, thereby establishing their infinite quantity.

Numbers derived by adding one to the product of the initial primes are designated as Euclid numbers. The first five of these numbers are prime, whereas the sixth,

§67§ + ( §1617§ ⋅<!-- ⋅ --> §2122§ ⋅<!-- ⋅ --> §2627§ ⋅<!-- ⋅ --> §3132§ ⋅<!-- ⋅ --> §3637§ ⋅<!-- ⋅ --> §4142§ ) = 30031 = 59 ⋅<!-- ⋅ --> 509 , {\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,}

is a composite number.

Formulas for Prime Numbers

No efficient formula for generating prime numbers has been discovered. For instance, no non-constant polynomial, even one involving multiple variables, exclusively yields prime values. Nevertheless, various expressions exist that either encode all prime numbers or produce only prime numbers. One such formula, derived from Wilson's theorem, generates the number 2 multiple times while producing all other prime numbers precisely once. Additionally, a specific set of Diophantine equations, comprising nine variables and a single parameter, possesses the characteristic that the parameter is prime if and only if the corresponding system of equations has a solution within the set of natural numbers. This property allows for the derivation of a singular formula whose positive outputs are exclusively prime numbers.

Further instances of formulas capable of generating prime numbers are provided by Mills' theorem and a theorem attributed to Wright. These theorems posit the existence of real constants 11§ {\displaystyle A>1} and ${\displaystyle \mu }$, respectively, such that

${\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor }$

These expressions yield prime numbers for any natural number ⁠${\displaystyle n}$⁠ in the initial formula, and for any specified number of exponents in the subsequent formula. The notation ${\displaystyle \lfloor {}\cdot {}\rfloor }$ denotes the floor function, which returns the greatest integer less than or equal to the argument. Nonetheless, these formulas lack practical utility for prime generation, as the values of ⁠${\displaystyle A}$⁠ or ${\displaystyle \mu .}$ must first be computed using pre-existing prime numbers.

Unresolved Questions

Numerous conjectures concerning prime numbers have been proposed. Despite their often elementary formulations, many of these conjectures have resisted proof for decades; for instance, all four of Landau's problems, posed in 1912, remain unresolved. A prominent example is Goldbach's conjecture, which postulates that every even integer ⁠${\displaystyle n}$⁠ exceeding ⁠§2526§ {\displaystyle 2} ⁠ can be expressed as the sum of two prime numbers. By 2014, this conjecture had been computationally verified for all integers up to n = §4647§ ⋅<!-- ⋅ --> §5253§ §5556§ . {\displaystyle n=4\cdot 10^{18}.} While Goldbach's conjecture remains unproven, weaker related statements have been established; for instance, Vinogradov's theorem demonstrates that any sufficiently large odd integer can be represented as the sum of three prime numbers. Furthermore, Chen's theorem asserts that every sufficiently large even number can be expressed as the sum of a prime and a semiprime, which is defined as the product of two primes. Additionally, any even integer exceeding 10 can be decomposed into the sum of six primes. The field of number theory dedicated to investigating these types of questions is known as additive number theory.

A distinct category of mathematical inquiry pertains to prime gaps, which are defined as the differences observed between successive prime numbers. The existence of prime gaps of arbitrary magnitude is demonstrable by observing that the sequence ${\displaystyle n!+2,n!+3,\dots ,n!+n}$ comprises n −<!-- − --> §5859§ {\displaystyle n-1} composite numbers for any natural number ${\displaystyle n.}$ Nevertheless, substantial prime gaps manifest considerably earlier than this theoretical construction suggests. For instance, the initial prime gap of length 8 is situated between the primes 89 and 97, a value significantly less than ${\displaystyle 8!=40320.}$ The twin prime conjecture posits the existence of an infinite number of twin primes, which are pairs of prime numbers differing by 2. More broadly, Polignac's conjecture asserts that for every positive integer ${\displaystyle k,}$, there exist infinitely many pairs of consecutive prime numbers whose difference is ${\displaystyle 2k.}$ Several conjectures, including those by Andrica, Brocard, Legendre, and Oppermann, propose that the maximum prime gaps within the range from 1 to ⁠${\displaystyle n}$⁠ should not exceed approximately ${\displaystyle {\sqrt {n}},}$, a consequence known to derive from the Riemann hypothesis. In contrast, the significantly more stringent Cramér conjecture posits the largest gap size as ⁠${\displaystyle O((\log n)^{2})}$⁠. The concept of prime gaps can be extended to prime ⁠${\displaystyle k}$⁠-tuples, which represent patterns of differences among more than two prime numbers. The first Hardy–Littlewood conjecture addresses their infinitude and density, a proposition supported by the heuristic observation that prime numbers exhibit behavior analogous to a random sequence of numbers, with a density determined by the prime number theorem.

Analytic properties

Analytic number theory investigates number theory utilizing the framework of continuous functions, limits, infinite series, and associated mathematical concepts pertaining to infinity and infinitesimals.

The field of study originated with Leonhard Euler, whose initial significant contribution was the resolution of the Basel problem. This problem sought the value of the infinite series §67§ + §1314§ §1516§ + §2526§ §2728§ + §3738§ §3940§ + … , {\displaystyle 1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots ,} , which is now identified as the value ${\displaystyle \zeta (2)}$ of the Riemann zeta function. This function exhibits a strong relationship with prime numbers and is central to the Riemann hypothesis, one of mathematics' most profound unresolved problems. Euler demonstrated that ⁠${\displaystyle \zeta (2)=\pi ^{2}/6}$⁠. The inverse of this value, ⁠${\displaystyle 6/\pi ^{2}}$⁠, represents the limiting probability that two randomly chosen integers from a substantial range will be relatively prime, meaning they share no common factors.

The macroscopic distribution of prime numbers, including the quantity of primes below a specified large threshold, is characterized by the prime number theorem. However, an efficient formula for determining the ⁠${\displaystyle n}$⁠-th prime remains undiscovered. Dirichlet's theorem on arithmetic progressions, in its fundamental formulation, posits that linear polynomials

${\displaystyle p(n)=a+bn}$

where integers ⁠${\displaystyle a}$⁠ and ⁠${\displaystyle b}$⁠ are relatively prime, yield an infinite number of prime values. More advanced versions of the theorem assert that the sum of the reciprocals of these prime values diverges, and that distinct linear polynomials sharing the same parameter ⁠${\displaystyle b}$⁠ exhibit approximately equivalent proportions of primes. While conjectures regarding the proportions of primes generated by higher-degree polynomials have been proposed, these remain unproven. Furthermore, it is currently unknown whether any quadratic polynomial can produce prime numbers infinitely often when evaluated with integer inputs.

Analytical Demonstration of Euclid's Theorem

Euler's proof, establishing the infinitude of prime numbers, involves an examination of the sums of their reciprocals.

§89§ §1011§ + §1819§ §2021§ + §2829§ §3031§ + §3839§ §4041§ + ⋯ + §5354§ p . {\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.}

Euler demonstrated that for any arbitrary real number ⁠${\displaystyle x}$⁠, a prime ⁠${\displaystyle p}$⁠ exists such that this sum exceeds ⁠${\displaystyle x}$⁠. This finding establishes the infinitude of prime numbers, as a finite set of primes would imply the sum reaches a finite maximum at the largest prime, rather than continuously surpassing every ⁠${\displaystyle x}$⁠. Mertens' second theorem provides a more precise description of this sum's growth rate. In contrast, the sum

§89§ §1112§ §1415§ + §2425§ §2728§ §3031§ + §4041§ §4344§ §4647§ + ⋯ + §6162§ n §6768§ {\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}}

does not diverge to infinity as ⁠${\displaystyle n}$⁠ approaches infinity. This phenomenon is detailed in the Basel problem. Consequently, prime numbers exhibit a higher frequency of occurrence compared to the squares of natural numbers, despite both sets being infinite. Brun's theorem further posits that the sum of the reciprocals of twin primes,

( §1213§ §1415§ + §2223§ §2425§ ) + ( §4041§ §4243§ + §5051§ §5253§ ) + ( §6869§ §7071§ + §7879§ §8081§ ) + ⋯ , {\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots ,}

is finite. Brun's theorem establishes that Euler's method cannot be applied to resolve the twin prime conjecture, which posits the existence of an infinite number of twin primes.

The Enumeration of Primes Up to a Specified Limit

The prime-counting function, denoted as ${\displaystyle \pi (n)}$, quantifies the number of prime numbers that do not exceed ⁠${\displaystyle n}$⁠. For instance, ⁠${\displaystyle \pi (11)=5}$⁠, reflecting the presence of five prime numbers less than or equal to 11. Algorithms like the Meissel–Lehmer algorithm enable the precise calculation of ${\displaystyle \pi (n)}$ with greater efficiency than enumerating every prime number up to ⁠${\displaystyle n}$⁠. The Prime Number Theorem asserts that ${\displaystyle \pi (n)}$ exhibits asymptotic behavior equivalent to ⁠${\displaystyle n/\log n}$⁠, a relationship formally expressed as:

${\displaystyle \pi (n)\sim {\frac {n}{\log n}},}$

This signifies that the ratio of ${\displaystyle \pi (n)}$ to the right-hand fraction converges to 1 as ⁠${\displaystyle n}$⁠ tends towards infinity. Consequently, the probability that a randomly selected integer smaller than ⁠${\displaystyle n}$⁠ is prime is approximately inversely proportional to the number of digits in ⁠${\displaystyle n}$⁠. Furthermore, this theorem indicates that the ⁠${\displaystyle n}$⁠th prime number scales proportionally with ${\displaystyle n\log n}$, implying that the mean magnitude of a prime gap is proportional to ⁠${\displaystyle \log n}$⁠. A more precise estimation for ${\displaystyle \pi (n)}$ is provided by the offset logarithmic integral.

${\displaystyle \pi (n)\sim \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\log t}}.}$

Arithmetic Progressions

An arithmetic progression constitutes a finite or infinite series of numbers where the difference between successive terms remains constant. This consistent difference is termed the modulus of the progression. For instance,

${\displaystyle 3,12,21,30,39,...,}$

This sequence represents an infinite arithmetic progression with a modulus of 9. Within an arithmetic progression, all terms yield an identical remainder upon division by the modulus; in this specific instance, the remainder is 3. Since both the modulus (9) and the remainder (3) are divisible by 3, every element within this sequence is also a multiple of 3. Consequently, this progression includes only a single prime number, which is 3. More broadly, an infinite progression of the form

${\displaystyle a,a+q,a+2q,a+3q,\dots }$

An arithmetic progression can contain more than one prime number exclusively when its remainder ⁠${\displaystyle a}$⁠ and modulus ⁠${\displaystyle q}$⁠ are coprime. Should these values be coprime, Dirichlet's theorem on arithmetic progressions guarantees the existence of an infinite number of primes within that progression.

The Green–Tao theorem demonstrates the existence of finite arithmetic progressions of arbitrary length composed entirely of prime numbers.

Prime Values Generated by Quadratic Polynomials

Euler observed that the mathematical function

${\displaystyle n^{2}-n+41}$

This function generates prime numbers for ⁠§78§≤n≤40{\displaystyle 1\leq n\leq 40}⁠, yet composite numbers emerge within its subsequent outputs. The investigation into this observation contributed to the development of profound algebraic number theory concerning Heegner numbers and the class number problem. Hardy–Littlewood conjecture F posits the density of prime numbers among the outputs of quadratic polynomials with integer coefficients, expressed through the logarithmic integral and the polynomial's own coefficients. To date, no quadratic polynomial has been demonstrated to produce an infinite sequence of prime values.

The Ulam spiral organizes natural numbers within a two-dimensional grid, forming concentric squares that spiral outward from the origin, with prime numbers distinctly marked. A visual inspection reveals that primes tend to aggregate along specific diagonals rather than others, implying that certain quadratic polynomials generate prime values with greater frequency.

The Zeta Function and the Riemann Hypothesis

The Riemann hypothesis, formulated in 1859 and recognized as one of the Millennium Prize Problems, represents a prominent unsolved mathematical enigma. It seeks to determine the precise locations of the zeros of the Riemann zeta function, denoted as ${\displaystyle \zeta (s)}$. This function operates as an analytic function across the complex numbers. For complex numbers ⁠${\displaystyle s}$⁠ possessing a real part exceeding one, it can be expressed equivalently as both an infinite summation over all integers and an infinite product over the prime numbers.

ζ<!-- ζ -->(s)=∑<!-- ∑ -->n=§2627§∞§3638§ns=∏p prime§6467§§6870§−p−s.{\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}.}

Euler's discovery of this sum-product equality is known as an Euler product. Derivable from the fundamental theorem of arithmetic, the Euler product elucidates the profound relationship between the zeta function and prime numbers. This principle also furnishes an alternative proof for the infinitude of prime numbers: assuming a finite number of primes, the sum-product equality would hold at ⁠s = §1112§ {\displaystyle s=1} ⁠. However, at this point, the sum (the harmonic series ⁠§2930§ + §3637§ §3839§ + §4849§ §5051§ + … {\displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots } ⁠) would diverge, whereas the product would remain finite, leading to a logical contradiction.

The Riemann hypothesis posits that all zeros of the zeta function are either negative even integers or complex numbers possessing a real part of 1/2. The initial demonstration of the prime number theorem relied on a weaker version of this hypothesis, specifically that no zeros exist with a real part of 1; however, subsequent, more elementary proofs have since emerged. Riemann's explicit formula allows the prime-counting function to be articulated as a sum, where each constituent term originates from a zero of the zeta function. The primary component of this summation is the logarithmic integral, with the residual terms inducing oscillations around this main component. Consequently, these zeros govern the regularity of prime number distribution. Should the Riemann hypothesis prove correct, these fluctuations would be minimal, and the asymptotic distribution of primes, as established by the prime number theorem, would extend to significantly shorter intervals (approximately the square root of ⁠${\displaystyle x}$⁠ for intervals proximate to ⁠${\displaystyle x}$⁠).

Abstract algebra

Modular arithmetic and finite fields

From the perspective of abstract algebra, the capacity for division implies that modular arithmetic with a prime modulus constitutes a field, or more precisely, a finite field. In contrast, other moduli establish only a ring, not a field.

Modular arithmetic provides a framework for articulating various theorems concerning prime numbers. For example, Fermat's Little Theorem asserts that if a ≢ §1011§ {\displaystyle a\not \equiv 0} (mod ⁠${\displaystyle p}$⁠), then a p −<!-- − --> §5354§ ≡ §6061§ {\displaystyle a^{p-1}\equiv 1} (mod ⁠${\displaystyle p}$⁠). Aggregating this result across all possible values of ⁠${\displaystyle a}$⁠ yields the following equation:

∑<!-- ∑ --> a = §1516§ p − §2425§ a p − §3738§ ≡ ( p − §5152§ ) ⋅ §5859§ ≡ − §6667§ ( mod p ) , {\displaystyle \sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},}

This equation holds true exclusively when ⁠${\displaystyle p}$⁠ is a prime number. Giuga's conjecture posits that this equation also serves as a sufficient condition for ⁠${\displaystyle p}$⁠ to be prime. Furthermore, Wilson's Theorem establishes that an integer 47§ {\displaystyle p>1} is prime if and only if its factorial, ( p −<!-- − --> §6970§ ) ! {\displaystyle (p-1)!} , is congruent to −<!-- − --> §9293§ {\displaystyle -1} modulo ⁠${\displaystyle p}$⁠. This condition cannot be satisfied for a composite number ⁠${\displaystyle n=r\cdot s}$⁠, because at least one of its factors divides both n and ⁠( n −<!-- − --> §163164§ ) ! {\displaystyle (n-1)!} ⁠, rendering the congruence ( n −<!-- − --> §191192§ ) ! ≡ − §203204§ ( mod n ) {\displaystyle (n-1)!\equiv -1{\pmod {n}}} impossible.

p-adic Numbers

The ⁠${\displaystyle p}$⁠-adic order, denoted as ${\displaystyle \nu _{p}(n)}$ for an integer ⁠${\displaystyle n}$⁠, quantifies the exponent of ⁠${\displaystyle p}$⁠ in the prime factorization of ⁠${\displaystyle n}$⁠.

The conceptual framework encompassing order, absolute value, and their derived complete fields can be extended to algebraic number fields. This generalization involves valuations, which are specific mappings from the multiplicative group of a field to a totally ordered additive group (also termed orders); absolute values, defined as multiplicative mappings from the field to the real numbers (also known as norms); and places, which represent extensions to complete fields where the original field forms a dense subset (also referred to as completions). For instance, the extension from rational numbers to real numbers exemplifies a place where the distance between numbers is determined by the standard absolute value of their difference. While the logarithm of the absolute value could serve as a corresponding mapping to an additive group, it does not fully satisfy the criteria for a valuation. Ostrowski's theorem asserts that, under a natural equivalence relation, the real numbers and ⁠${\displaystyle p}$⁠-adic numbers, along with their associated orders and absolute values, constitute the sole valuations, absolute values, and places defined on the rational numbers. The local–global principle facilitates the resolution of specific problems concerning rational numbers by synthesizing solutions derived from each of their respective places, thereby re-emphasizing the fundamental role of prime numbers in number theory.

Prime Elements within a Ring

A commutative ring constitutes an algebraic structure characterized by defined operations of addition, subtraction, and multiplication. The set of integers forms a ring, and the concept of prime numbers within the integers has been extended to general rings through two distinct classifications: prime elements and irreducible elements. An element ⁠${\displaystyle p}$⁠ within a ring ⁠${\displaystyle R}$⁠ is designated as prime if it is non-zero, lacks a multiplicative inverse (i.e., it is not a unit), and satisfies the condition that whenever ⁠${\displaystyle p}$⁠ divides the product ${\displaystyle xy}$ of two elements from ⁠${\displaystyle R}$⁠, it must also divide at least one of ⁠${\displaystyle x}$⁠ or ⁠${\displaystyle y}$⁠. Conversely, an element is deemed irreducible if it is neither a unit nor expressible as the product of two other non-unit elements. Within the ring of integers, prime and irreducible elements constitute an identical set.

${\displaystyle \{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,.}$

Within an arbitrary ring, every prime element is necessarily irreducible. However, the converse of this statement is not universally true, though it does hold specifically for unique factorization domains.

The fundamental theorem of arithmetic is inherently valid within unique factorization domains. A notable instance of such a domain is the Gaussian integers, denoted as ⁠${\displaystyle \mathbb {Z} [i]}$⁠. This ring comprises complex numbers structured as ${\displaystyle a+bi}$, where ⁠${\displaystyle i}$⁠ represents the imaginary unit, and ⁠${\displaystyle a}$⁠ and ⁠${\displaystyle b}$⁠ are integers. The prime elements within this domain are termed Gaussian primes. It is important to note that not all integers that are prime in the set of integers retain their primality within the Gaussian integers. For example, the integer 2 can be expressed as the product of two Gaussian primes: §108109§ + i {\displaystyle 1+i} and ⁠§129130§ − i {\displaystyle 1-i} ⁠. Rational primes (i.e., prime numbers in the set of integers) that are congruent to 3 modulo 4 are classified as Gaussian primes, whereas those congruent to 1 modulo 4 are not. This distinction arises from Fermat's theorem on sums of two squares, which posits that an odd prime ⁠${\displaystyle p}$⁠ can be expressed as the sum of two squares, specifically ⁠p = x §178179§ + y §188189§ {\displaystyle p=x^{2}+y^{2}} ⁠. Consequently, it is factorable as ⁠${\displaystyle p=(x+iy)(x-iy)}$⁠, precisely when ⁠${\displaystyle p}$⁠ is congruent to 1 modulo 4.

Prime ideals

Not every ring constitutes a unique factorization domain. For example, the ring of numbers ${\displaystyle a+b{\sqrt {-5}}}$ (where ⁠${\displaystyle a}$⁠ and ⁠${\displaystyle b}$⁠ are integers) does not exhibit unique factorization. This is demonstrated by the number ${\displaystyle 21}$, which possesses two distinct factorizations: ⁠§8889§ = §9293§ ⋅<!-- ⋅ --> §9798§ = ( §103104§ + §107108§ −<!-- − --> §114115§ ) ( §122123§ − §127128§ −<!-- − --> §134135§ ) {\displaystyle 21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})} ⁠. In this instance, none of the four factors can be further reduced, thereby precluding unique factorization. To extend unique factorization to a broader class of rings, the concept of a number is superseded by that of an ideal, which is defined as a subset of a ring's elements that is closed under addition (containing all sums of pairs of its elements) and under multiplication by any ring element.

The spectrum of a ring defines a geometric space where its points correspond to the prime ideals of that ring. This concept also proves beneficial in arithmetic geometry, where numerous principles are shared between geometry and number theory. For instance, the factorization or ramification of prime ideals upon extension to a larger field, a fundamental challenge in algebraic number theory, exhibits parallels with geometric ramification. Such concepts can even aid in purely number-theoretic inquiries focused exclusively on integers. For example, the application of prime ideals within the ring of integers of quadratic number fields facilitates the proof of quadratic reciprocity, a theorem addressing the existence of square roots modulo integer prime numbers. Initial efforts to establish Fermat's Last Theorem prompted Kummer to introduce regular primes, which are integer prime numbers associated with the breakdown of unique factorization in cyclotomic integers. Chebotarev's density theorem addresses the inquiry into the number of integer prime numbers that factor into multiple prime ideals within an algebraic number field; when applied to cyclotomic integers, this theorem encompasses Dirichlet's theorem on primes in arithmetic progressions as a specific instance.

Group theory

Within the theory of finite groups, the Sylow theorems establish that if a power of a prime number, specifically ${\displaystyle p^{n}}$, divides the order of a group, then the group necessarily possesses a subgroup of order ⁠${\displaystyle p^{n}}$⁠. Furthermore, Lagrange's theorem dictates that any group with a prime order is cyclic, while Burnside's theorem asserts that any group whose order is divisible by precisely two primes is solvable.

Computational methods

Historically, number theory, and specifically the study of prime numbers, was widely regarded as the quintessential example of pure mathematics, possessing no practical applications beyond the use of prime-numbered gear teeth to ensure uniform wear distribution. Notably, number theorists like the British mathematician G. H. Hardy took pride in conducting research devoid of any military relevance.

This perception of number theory's inherent purity was fundamentally altered in the 1970s with the public disclosure that prime numbers could form the foundational basis for developing public-key cryptography algorithms. These practical applications have spurred extensive research into algorithms for computations involving prime numbers, particularly focusing on primality testing—methods designed to ascertain whether a given number is prime. The most rudimentary primality testing procedure, trial division, proves inefficient for large numbers due to its computational slowness. While one category of contemporary primality tests is suitable for arbitrary numbers, more computationally efficient tests exist for numbers exhibiting specific characteristics. The majority of primality tests merely indicate whether their input argument is prime or composite. Algorithms that additionally furnish a prime factor (or all prime factors) of composite inputs are termed factorization algorithms. Furthermore, prime numbers find utility in computing for applications such as checksums, hash tables, and pseudorandom number generators.

Trial division

The fundamental approach for ascertaining the primality of a specified integer ⁠${\displaystyle n}$⁠ is known as trial division. This procedure involves dividing ⁠${\displaystyle n}$⁠ by every integer ranging from 2 up to its square root, ⁠${\displaystyle n}$⁠. If any of these integers divides ⁠${\displaystyle n}$⁠ without a remainder, then ⁠${\displaystyle n}$⁠ is classified as composite; otherwise, it is deemed prime. It is unnecessary to examine integers exceeding the square root, given that if ⁠${\displaystyle n=a\cdot b}$⁠, at least one of the factors, ⁠${\displaystyle a}$⁠ or ⁠${\displaystyle b}$⁠, must be less than or equal to the square root of ⁠${\displaystyle n}$⁠. A further optimization involves restricting the divisors within this range to prime numbers exclusively. For example, to determine the primality of 37, this technique entails dividing it by the prime numbers between 2 and ⁠§182183§ {\displaystyle {\sqrt {37}}} ⁠, specifically 2, 3, and 5. Since each division yields a non-zero remainder, 37 is confirmed as a prime number.

While conceptually straightforward, this method becomes unfeasible for assessing the primality of substantial integers, as the requisite number of tests escalates exponentially with the number of digits in the integer. Nevertheless, trial division retains utility, often employed with a divisor limit smaller than the square root, to rapidly identify composite numbers possessing minor factors, prior to the application of more sophisticated algorithms to integers that successfully pass this initial screening.

Sieve Methods

Prior to the advent of computers, mathematical tables enumerating prime numbers or their factorizations up to a specified threshold were routinely published. The most ancient recognized algorithm for compiling a list of prime numbers is designated the Sieve of Eratosthenes. An optimized variant of this method has been developed. A distinct sieving technique, offering superior asymptotic efficiency for this particular problem, is the Sieve of Atkin. Within advanced mathematical contexts, sieve theory extends analogous methodologies to address a broader spectrum of problems.

Distinction Between Primality Testing and Primality Proving

Modern primality tests, particularly those designed for speed, often employ probabilistic (Monte Carlo) algorithms to determine if an arbitrary number ⁠${\displaystyle n}$⁠ is prime. These methods inherently carry a minor, random probability of yielding an erroneous result. As an illustration, the Solovay–Strassen primality test, when applied to a number ⁠${\displaystyle p}$⁠, involves selecting a random integer ⁠${\displaystyle a}$⁠ from the range [2, p −<!-- − --> §6566§ {\displaystyle p-2} ]. It then utilizes modular exponentiation to ascertain if a ( p −<!-- − --> §9293§ ) / §100101§ ± §107108§ {\displaystyle a^{(p-1)/2}\pm 1} is divisible by ⁠${\displaystyle p}$⁠. A positive result indicates primality, while a negative result suggests compositeness. Should ⁠${\displaystyle p}$⁠ genuinely be prime, the test will invariably return a positive affirmation. However, if ⁠${\displaystyle p}$⁠ is composite, the probability of a false positive (answering yes) is at most 1/2, while the probability of correctly identifying it as composite (answering no) is at least 1/2. When this test is iteratively performed ⁠${\displaystyle n}$⁠ times on the same number, the likelihood of a composite number consistently passing all iterations is bounded by ⁠§196197§ / §203204§ n {\displaystyle 1/2^{n}} ⁠. This exponential decrease in probability significantly enhances confidence that a number successfully enduring repeated tests is indeed prime, though it does not provide absolute certainty. Conversely, any single failure of the test definitively establishes the number as composite. A composite number that erroneously passes such a primality test is termed a pseudoprime.

In contrast, certain alternative algorithms offer a guarantee of absolute correctness in their determinations: prime numbers are unfailingly identified as prime, and composite numbers are consistently recognized as composite. Trial division exemplifies such a method. Algorithms that produce verifiably correct outputs encompass both deterministic (non-randomized) approaches, like the AKS primality test, and randomized Las Vegas algorithms. In the latter, random selections made during execution do not compromise the accuracy of the final result, as observed in specific implementations of elliptic curve primality proving. Upon determining a number's primality, the elliptic curve method generates a primality certificate, which can be rapidly validated. While the elliptic curve primality test is empirically the most efficient among guaranteed-correct methods, its runtime analysis relies on heuristic reasoning rather than formal mathematical proofs. Conversely, the AKS primality test possesses a mathematically established time complexity, yet it exhibits slower practical performance compared to elliptic curve primality proving. These techniques facilitate the generation of large random prime numbers by iteratively producing and testing random integers until a prime is identified. In this process, an initial, faster probabilistic test can efficiently filter out the majority of composite numbers, reserving the more computationally intensive, guaranteed-correct algorithms for final verification of the remaining candidates.

The subsequent table enumerates several of these tests. Their operational duration is expressed in relation to ⁠${\displaystyle n}$⁠, which represents the integer under examination, and for probabilistic algorithms, the quantity ⁠${\displaystyle k}$⁠, denoting the number of iterations performed. Furthermore, ${\displaystyle \varepsilon }$ signifies an arbitrarily small positive value, and "log" refers to the logarithm with an unspecified base. The big O notation implies that each time bound necessitates multiplication by a constant factor to convert it from dimensionless units into temporal units; this factor is contingent upon implementation specifics, such as the computing hardware employed, but remains independent of the input parameters ⁠${\displaystyle n}$⁠ and ⁠${\displaystyle k}$⁠.

Specialized Algorithms and the Largest Identified Prime Numbers

Beyond the general primality tests applicable to any natural number, certain numbers possessing a specific structure can undergo primality assessment with greater efficiency. For instance, the Lucas–Lehmer primality test can deterministically ascertain the primality of a Mersenne number (defined as one less than a power of two) within the computational timeframe equivalent to a single iteration of the Miller–Rabin test. Consequently, since 1992 (up to October 2024), the largest known prime has consistently been a Mersenne prime. A prevailing conjecture posits the existence of an infinite number of Mersenne primes.

The subsequent table presents the largest identified prime numbers across different classifications. Several of these primes have been discovered through distributed computing initiatives. In 2009, the Great Internet Mersenne Prime Search project received a US$100,000 award for being the first to identify a prime number comprising at least 10 million digits. The Electronic Frontier Foundation additionally provides incentives of $150,000 and $250,000 for the discovery of primes with a minimum of 100 million digits and 1 billion digits, respectively.

Integer Factorization

For a given composite integer ⁠${\displaystyle n}$⁠, the process of identifying one or all of its prime factors is termed factorization of ⁠${\displaystyle n}$⁠. This operation presents a considerably greater challenge than primality testing; despite the existence of numerous factorization algorithms, they generally exhibit slower performance compared to the most efficient primality testing methodologies. Techniques such as trial division and Pollard's rho algorithm are applicable for discovering very small factors of ⁠${\displaystyle n}$⁠, while elliptic curve factorization proves effective when ⁠${\displaystyle n}$⁠ possesses factors of moderate magnitude. General-purpose methods suitable for arbitrarily large numbers, irrespective of their factor sizes, include the quadratic sieve and the general number field sieve. Analogous to primality testing, certain factorization algorithms are designed for inputs with specific structures, such as the special number field sieve. As of December 2019, the largest number successfully factored by a general-purpose algorithm was RSA-240, which consists of 240 decimal digits (795 bits) and represents the product of two substantial prime numbers.

Shor's algorithm offers the capability to factor any integer within a polynomial number of steps when executed on a quantum computer. Nevertheless, contemporary technological limitations restrict the application of this algorithm to only very small numbers. As of October 2012, the maximum integer successfully factored by a quantum computer employing Shor's algorithm was 21.

Additional Computational Applications

Numerous public-key cryptographic algorithms, including RSA and the Diffie–Hellman key exchange, fundamentally rely on large prime numbers, with 2048-bit primes being a prevalent standard. RSA's security paradigm is predicated on the computational asymmetry between multiplying two large prime numbers, ⁠${\displaystyle x}$⁠ and ⁠${\displaystyle y}$⁠, and factoring their product, ${\displaystyle xy}$, to retrieve the original primes ⁠${\displaystyle x}$⁠ and ⁠${\displaystyle y}$⁠ (which are assumed to be coprime). Conversely, the Diffie–Hellman key exchange leverages the existence of efficient algorithms for modular exponentiation (specifically, computing ⁠${\displaystyle a^{b}{\bmod {c}}}$⁠), contrasting with the perceived computational intractability of its inverse, the discrete logarithm problem.

Prime numbers find extensive application in the design of hash tables. For example, the foundational universal hashing scheme proposed by Carter and Wegman employed random linear functions computed modulo large prime numbers to generate hash functions. Subsequently, Carter and Wegman extended this methodology to achieve ⁠${\displaystyle k}$⁠-independent hashing through the utilization of higher-degree polynomials, also operating modulo large primes. Beyond their role in hash function construction, prime numbers are also critical for determining the size of hash tables in quadratic probing schemes, thereby guaranteeing that the probe sequence effectively traverses the entire table.

The mathematical properties of prime numbers underpin several checksum algorithms. For example, the checksums incorporated into International Standard Book Numbers (ISBNs) are derived by computing the remainder of the number when divided by 11, which is a prime. The primality of 11 enables this method to effectively identify both single-digit errors and transpositions of adjacent digits. Furthermore, the Adler-32 checksum algorithm employs arithmetic modulo 65521, which represents the largest prime number smaller than ⁠§89§ 16 {\displaystyle 2^{16}} ⁠. Additionally, prime numbers are integral to various pseudorandom number generators, such as linear congruential generators and the Mersenne Twister.

Other Applications

While central to number theory, prime numbers also possess significant applications across diverse mathematical domains, including abstract algebra and elementary geometry. For instance, configurations exist where a prime number of points can be arranged on a two-dimensional grid such that no three points are collinear, or alternatively, such that any triangle formed by three of these points encloses a substantial area. A further illustration is Eisenstein's criterion, which provides a test for polynomial irreducibility by examining the divisibility of its coefficients by a prime number and its square.

The fundamental nature of prime numbers has led to their generalization in various mathematical disciplines. Typically, the term "prime" denotes minimality or indecomposability within a specific mathematical context. For instance, the prime field associated with a given field represents its minimal subfield encompassing both 0 and 1. This prime field is either the field of rational numbers or a finite field characterized by a prime number of elements, which explains its nomenclature. Furthermore, the term "prime" frequently implies a secondary meaning: the capacity for any object to be uniquely decomposed into its fundamental prime constituents. In knot theory, for example, a prime knot is defined as an indecomposable knot, meaning it cannot be expressed as the connected sum of two non-trivial knots. Every knot possesses a unique representation as a connected sum of prime knots. The prime decomposition of 3-manifolds serves as another illustration of this principle.

Beyond their applications in mathematics and computing, prime numbers exhibit potential connections to quantum mechanics and have been employed metaphorically in artistic and literary contexts. Additionally, they have found utility in evolutionary biology for elucidating the life cycles of cicadas.

Constructible Polygons and Polygon Partitions

Fermat primes are defined as prime numbers conforming to the structure:

F k = §1718§ §2122§ k + §3233§ , {\displaystyle F_{k}=2^{2^{k}}+1,}

where ⁠${\displaystyle k}$⁠ denotes a nonnegative integer. These numbers are named in honor of Pierre de Fermat, who hypothesized that all numbers of this form are prime. While the initial five Fermat numbers—3, 5, 17, 257, and 65,537—are prime, ${\displaystyle F_{5}}$ is composite, a characteristic shared by all other Fermat numbers verified up to 2017. A regular ⁠${\displaystyle n}$⁠-gon can be constructed using only a straightedge and compass if and only if its odd prime factors (should any exist) are distinct Fermat primes. Similarly, a regular ⁠${\displaystyle n}$⁠-gon can be constructed using a straightedge, compass, and an angle trisector if and only if the prime factors of ⁠${\displaystyle n}$⁠ consist of any number of factors of 2 or 3, combined with a (potentially empty) set of distinct Pierpont primes, which are primes of the form ⁠§120121§ a §128129§ b + §137138§ {\displaystyle 2^{a}3^{b}+1} ⁠.

Any convex polygon can be partitioned into ⁠${\displaystyle n}$⁠ smaller convex polygons, each possessing equal area and equal perimeter, provided that ⁠${\displaystyle n}$⁠ is a power of a prime number; however, this property remains unconfirmed for other values of ⁠${\displaystyle n}$⁠.

Quantum Mechanics

Since the 1970s, commencing with the research conducted by Hugh Montgomery and Freeman Dyson, mathematicians and physicists have posited a correlation between the zeros of the Riemann zeta function and the energy levels observed in quantum systems. Furthermore, prime numbers hold considerable importance within quantum information science, owing to their role in mathematical constructs like mutually unbiased bases and symmetric informationally complete positive-operator-valued measures.

Biology

The genus of cicadas, Magicicada, employs an evolutionary strategy that incorporates prime numbers. These insects spend the majority of their existence as subterranean larvae, only to pupate and emerge from their burrows after precisely 7, 13, or 17 years. Following emergence, they engage in flight, reproduction, and subsequently perish within a few weeks. Biologists postulate that these prime-numbered breeding cycle durations have evolved as a mechanism to preclude predator synchronization with their life cycles. Conversely, the multi-year intervals between flowering events in bamboo species are conjectured to be smooth numbers, characterized by factorizations containing solely small prime numbers.

Arts and Literature

Prime numbers have exerted a notable influence on numerous artists and literary figures. The French composer Olivier Messiaen, for instance, utilized prime numbers to construct ametrical music, drawing inspiration from "natural phenomena." In compositions such as La Nativité du Seigneur (1935) and Quatre études de rythme (1949–1950), Messiaen concurrently deploys musical motifs whose durations correspond to distinct prime numbers, thereby generating unpredictable rhythmic patterns. Specifically, the primes 41, 43, 47, and 53 are evident in the third étude, titled "Neumes rythmiques." Messiaen himself articulated that this compositional approach was "inspired by the movements of nature, movements of free and unequal durations."

In his science fiction novel Contact, the scientist Carl Sagan proposed that prime factorization could serve as a method for establishing two-dimensional image planes during communication with extraterrestrial intelligence, an concept he initially formulated informally with American astronomer Frank Drake in 1975. Mark Haddon's novel The Curious Incident of the Dog in the Night-Time features a narrator who structures the narrative sections using consecutive prime numbers, effectively conveying the psychological state of the protagonist, a mathematically talented adolescent with Asperger syndrome. Furthermore, prime numbers function as a metaphor for loneliness and isolation in Paolo Giordano's novel The Solitude of Prime Numbers, where they are depicted as "outsiders" within the set of integers.

References

"Prime number." Encyclopedia of Mathematics. EMS Press, 2001 [1994].

• "Prime number". Encyclopedia of Mathematics. EMS Press. 2001 [1994].In Our Time, BBC.
• "Teacher package: Prime numbers." Plus, December 1, 2008, produced by the Millennium Mathematics Project at the University of Cambridge.

• Prime factors calculator can factorize any positive integer up to 20 digits.
• Huge database of prime numbers.
• Prime Numbers up to 1 trillion. Archived 2021-02-27 at the Wayback Machine.