Editing Prime number (section)

== Elementary properties ==
=== Unique factorization ===
{{Main|Fundamental theorem of arithmetic}}

Writing a number as a product of prime numbers is called a ''prime factorization'' of the number. For example:
: <math>\begin{align}
   50 &= 2\times 5\times 5\\
   &=2\times 5^2.
 \end{align}</math>
The terms in the product are called ''prime factors''. The same prime factor may occur more than once; this example has two copies of the prime factor <math>5.</math> When a prime occurs multiple times, [[exponentiation]] can be used to group together multiple copies of the same prime number: for example, in the second way of writing the product above, <math>5^2</math> denotes the [[Square (algebra)|square]] or second power of {{tmath|>5}}.

The central importance of prime numbers to number theory and mathematics in general stems from the ''fundamental theorem of arithmetic''.<ref>{{cite book|title=The Nature of Mathematics
|first=Karl J.|last=Smith|edition=12th|publisher=Cengage Learning|year=2011|isbn=978-0-538-73758-6|page=188|url=https://books.google.com/books?id=Di0HyCgDYq8C&pg=PA188}}</ref> This theorem states that every integer larger than 1 can be written as a product of one or more primes. More strongly, this product is unique in the sense that any two prime factorizations of the same number will have the same numbers of copies of the same primes, although their ordering may differ.<ref>{{harvnb|Dudley|1978}}, [https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA16 Section 2, Theorem 2, p. 16]; {{cite book|title=Closing the Gap: The Quest to Understand Prime Numbers|title-link= Closing the Gap: The Quest to Understand Prime Numbers |first=Vicky|last=Neale|author-link=Vicky Neale|publisher=Oxford University Press|year=2017|isbn=978-0-19-109243-5|at=[https://books.google.com/books?id=T7Q1DwAAQBAJ&pg=PA107 p. 107]}}</ref> So, although there are many different ways of finding a factorization using an [[integer factorization]] algorithm, they all must produce the same result. Primes can thus be considered the "basic building blocks" of the natural numbers.<ref>{{cite book|title=The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics|first=Marcus|last=du Sautoy|author-link=Marcus du Sautoy|publisher=Harper Collins|year=2003|isbn=978-0-06-093558-0|page=[https://archive.org/details/musicofprimessea00dusa/page/23 23]|url=https://archive.org/details/musicofprimessea00dusa|url-access=registration}}</ref>

Some proofs of the uniqueness of prime factorizations are based on [[Euclid's lemma]]: If {{tmath|p}} is a prime number and {{tmath|p}} divides a product <math>ab</math> of integers {{tmath|a}} and <math>b,</math> then {{tmath|p}} divides {{tmath|a}} or {{tmath|p}} divides {{tmath|b}} (or both).<ref>{{harvnb|Dudley|1978}}, [https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA15 Section 2, Lemma 5, p. 15]; {{cite book|title=Mathematics for the Curious|first=Peter M.|last=Higgins|publisher=Oxford University Press |year=1998 |isbn=978-0-19-150050-3 |pages=77–78|url=https://books.google.com/books?id=LeYH8P8S9oQC&pg=PA77}}</ref> Conversely, if a number {{tmath|p}} has the property that when it divides a product it always divides at least one factor of the product, then {{tmath|p}} must be prime.<ref>{{cite book|title=A First Course in Abstract Algebra|first=Joseph J.|last=Rotman|edition=2nd|publisher=Prentice Hall|year=2000|isbn=978-0-13-011584-3|at=Problem 1.40, p. 56}}</ref>

=== Infinitude ===
{{Main|Euclid's theorem}}
There are [[infinitely]] many prime numbers. Another way of saying this is that the sequence
: <math>2, 3, 5, 7, 11, 13, ...</math>
of prime numbers never ends. This statement is referred to as ''Euclid's theorem'' in honor of the ancient Greek mathematician [[Euclid]], since the first known proof for this statement is attributed to him. Many more proofs of the infinitude of primes are known, including an [[mathematical analysis|analytical]] proof by [[Euler]], [[Christian Goldbach|Goldbach's]] [[Fermat number#Basic properties|proof]] based on [[Fermat number]]s,<ref>[http://www.math.dartmouth.edu/~euler/correspondence/letters/OO0722.pdf Letter] in [[Latin]] from Goldbach to Euler, July 1730.</ref> [[Hillel Furstenberg|Furstenberg's]] [[Furstenberg's proof of the infinitude of primes|proof using general topology]],<ref>{{Cite journal | last1=Furstenberg | first1=Harry | author1-link=Hillel Furstenberg | title=On the infinitude of primes | doi=10.2307/2307043 | year=1955 | journal=[[American Mathematical Monthly]]   | volume=62 | mr=0068566 | issue=5 | pages=353 | jstor=2307043 }}
</ref> and [[Ernst Kummer|Kummer's]] elegant proof.<ref>{{cite book | last1=Ribenboim | first1=Paulo | author1-link=Paulo Ribenboim | title=The little book of bigger primes | publisher=Springer-Verlag | location=Berlin; New York | isbn=978-0-387-20169-6 | year=2004|page=4 | url=https://books.google.com/books?id=SvnTBwAAQBAJ&pg=PA5 }}</ref>

[[Euclid's theorem|Euclid's proof]]<ref>[[Euclid's Elements|Euclid's ''Elements'']], Book IX, Proposition 20. See [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html David Joyce's English translation of Euclid's proof] or {{cite book|url=https://babel.hathitrust.org/cgi/pt?id=umn.31951000084215o;view=1up;seq=95|title=The Elements of Euclid, With Dissertations|last=Williamson|first=James|publisher=[[Clarendon Press]]|year=1782|location=Oxford|page=63|oclc=642232959}}</ref> shows that every [[finite set|finite list]] of primes is incomplete. The key idea is to multiply together the primes in any given list and add <math>1.</math> If the list consists of the primes <math>p_1,p_2,\ldots, p_n,</math> this gives the number
: <math> N = 1 + p_1\cdot p_2\cdots p_n. </math>

By the fundamental theorem, {{tmath|N}} has a prime factorization
: <math> N =  p'_1\cdot p'_2\cdots p'_m </math>
with one or more prime factors. {{tmath|N}} is evenly divisible by each of these factors, but {{tmath|N}} has a remainder of one when divided by any of the prime numbers in the given list, so none of the prime factors of {{tmath|N}} can be in the given list. Because there is no finite list of all the primes, there must be infinitely many primes.

The numbers formed by adding one to the products of the smallest primes are called [[Euclid number]]s.<ref>{{cite book|title=Computational Recreations in Mathematica|first=Ilan|last=Vardi|publisher=Addison-Wesley|year=1991|isbn=978-0-201-52989-0|pages=82–89}}</ref> The first five of them are prime, but the sixth,
: <math>1+\big(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\big) = 30031 = 59\cdot 509,</math>
is a composite number.

=== Formulas for primes ===
{{main|Formula for primes}}

There is no known efficient formula for primes. For example, there is no non-constant [[polynomial]], even in several variables, that takes ''only'' prime values.<ref name="matiyasevich"/> However, there are numerous expressions that do encode all primes, or only primes. One possible formula is based on [[Wilson's theorem]] and generates the number 2 many times and all other primes exactly once.<ref>{{cite journal | last = Mackinnon | first = Nick | date = June 1987 | doi = 10.2307/3616496 | issue = 456 | pages = 113–114 | journal = [[The Mathematical Gazette]] | title = Prime number formulae | volume = 71| jstor = 3616496 | s2cid = 171537609 }}</ref> There is also a set of [[Diophantine equations]] in nine variables and one parameter with the following property: the parameter is prime if and only if the resulting system of equations has a solution over the natural numbers. This can be used to obtain a single formula with the property that all its ''positive'' values are prime.<ref name="matiyasevich">{{cite book | last = Matiyasevich | first = Yuri V. | author-link = Yuri Matiyasevich | year=1999 | chapter = Formulas for prime numbers | chapter-url=https://books.google.com/books?id=oLKlk5o6WroC&pg=PA13 | editor1-first=Serge | editor1-last = Tabachnikov | editor-link1=Sergei Tabachnikov| title = Kvant Selecta: Algebra and Analysis | volume = II | publisher = [[American Mathematical Society]] | isbn = 978-0-8218-1915-9 | pages=13–24}}</ref>

Other examples of prime-generating formulas come from [[Mills' theorem]] and a theorem of [[E. M. Wright|Wright]]. These assert that there are real constants <math>A>1</math> and <math>\mu</math> such that
: <math>\left \lfloor A^{3^n}\right \rfloor \text{ and } \left \lfloor 2^{\cdots^{2^{2^\mu}}} \right \rfloor</math>
are prime for any natural number {{tmath|n}} in the first formula, and any number of exponents in the second formula.<ref>{{cite journal |first=E.M. |last= Wright | author-link=E. M. Wright |title=A prime-representing function |journal=[[American Mathematical Monthly]] |volume=58 |issue=9 |year=1951 |pages=616–618 |jstor=2306356 |doi= 10.2307/2306356}}</ref> Here <math>\lfloor {}\cdot{} \rfloor</math> represents the [[floor function]], the largest integer less than or equal to the number in question. However, these are not useful for generating primes, as the primes must be generated first in order to compute the values of {{tmath|A}} or <math>\mu.</math><ref name="matiyasevich"/>

=== Open questions ===
{{Further|:Category:Conjectures about prime numbers}}

Many conjectures revolving about primes have been posed. Often having an elementary formulation, many of these conjectures have withstood proof for decades: all four of [[Landau's problems]] from 1912 are still unsolved.<ref>{{harvnb|Guy|2013}}, [https://books.google.com/books?id=EbLzBwAAQBAJ&pg=PR7 p. vii].</ref> One of them is [[Goldbach's conjecture]], which asserts that every even integer {{tmath|n}} greater than {{tmath|2}} can be written as a sum of two primes.<ref>{{harvnb|Guy|2013}}, [https://books.google.com/books?id=EbLzBwAAQBAJ&pg=PA105 C1 Goldbach's conjecture, pp. 105–107].</ref> {{As of|2014}}, this conjecture has been verified for all numbers up to <math>n=4\cdot 10^{18}.</math><ref>{{cite journal | last1 = Oliveira e Silva | first1 = Tomás | last2 = Herzog | first2 = Siegfried | last3 = Pardi | first3 = Silvio | doi = 10.1090/S0025-5718-2013-02787-1 | issue = 288 | journal = [[Mathematics of Computation]] | mr = 3194140 | pages = 2033–2060 | title = Empirical verification of the even Goldbach conjecture and computation of prime gaps up to <math>4\cdot10^{18}</math> | volume = 83 | year = 2014| doi-access = free }}</ref> Weaker statements than this have been proven; for example, [[Vinogradov's theorem]] says that every sufficiently large odd integer can be written as a sum of three primes.<ref>{{harvnb|Tao|2009}}, [https://books.google.com/books?id=NxnVAwAAQBAJ&pg=PA239 3.1 Structure and randomness in the prime numbers, pp. 239–247]. See especially p.&nbsp;239.</ref> [[Chen's theorem]] says that every sufficiently large even number can be expressed as the sum of a prime and a [[semiprime]] (the product of two primes).<ref>{{harvnb|Guy|2013}}, p. 159.</ref> Also, any even integer greater than 10 can be written as the sum of six primes.<ref>{{cite journal | last = Ramaré | first = Olivier | issue = 4 | journal = Annali della Scuola Normale Superiore di Pisa | mr = 1375315 | pages = 645–706 | title = On Šnirel'man's constant | url = https://www.numdam.org/item?id=ASNSP_1995_4_22_4_645_0 | volume = 22 | year = 1995 | access-date = 2018-01-23 | archive-date = 2022-02-09 | archive-url = https://web.archive.org/web/20220209175544/http://www.numdam.org/item/?id=ASNSP_1995_4_22_4_645_0 | url-status = dead }}</ref> The branch of number theory studying such questions is called [[additive number theory]].<ref>{{cite book | last = Rassias | first = Michael Th. | doi = 10.1007/978-3-319-57914-6 | isbn = 978-3-319-57912-2 | location = Cham | mr = 3674356 | page = vii | publisher = Springer | title = Goldbach's Problem: Selected Topics | url = https://books.google.com/books?id=ibwpDwAAQBAJ&pg=PP6 | year = 2017}}</ref>

Another type of problem concerns [[prime gap]]s, the differences between consecutive primes.
The existence of arbitrarily large prime gaps can be seen by noting that the sequence <math>n!+2,n!+3,\dots,n!+n</math> consists of <math>n-1</math> composite numbers, for any natural number <math>n.</math><ref>{{harvnb|Koshy|2002}}, [https://books.google.com/books?id=-9pg-4Pa19IC&pg=PA109 Theorem 2.14, p. 109]. {{harvnb|Riesel|1994}} gives a similar argument using the [[primorial]] in place of the factorial.</ref> However, large prime gaps occur much earlier than this argument shows.<ref name="riesel-gaps"/> For example, the first prime gap of length 8 is between the primes 89 and 97,<ref>{{cite OEIS|A100964|name=Smallest prime number that begins a prime gap of at least 2n}}</ref> much smaller than <math>8!=40320.</math> It is conjectured that there are infinitely many [[twin prime]]s, pairs of primes with difference 2; this is the [[twin prime conjecture]]. [[Polignac's conjecture]] states more generally that for every positive integer <math>k,</math> there are infinitely many pairs of consecutive primes that differ by <math>2k.</math><ref name="rib-gaps">{{harvnb|Ribenboim|2004}}, Gaps between primes, pp. 186–192.</ref>
[[Andrica's conjecture]],<ref name="rib-gaps"/> [[Brocard's conjecture]],<ref name="rib-183">{{harvnb|Ribenboim|2004}}, p. 183.</ref> [[Legendre's conjecture]],<ref name="chan">{{cite journal | last = Chan | first = Joel | title = Prime time! | journal = Math Horizons | volume = 3 | issue = 3 | date = February 1996 | pages = 23–25 | jstor = 25678057| doi = 10.1080/10724117.1996.11974965 }} Note that Chan lists Legendre's conjecture as "Sierpinski's Postulate".</ref> and [[Oppermann's conjecture]]<ref name="rib-183"/> all suggest that the largest gaps between primes from 1 to {{tmath|n}} should be at most approximately <math>\sqrt{n},</math> a result that is known to follow from the Riemann hypothesis, while the much stronger [[Cramér conjecture]] sets the largest gap size at {{tmath| O((\log n)^2) }}.<ref name="rib-gaps"/> Prime gaps can be generalized to [[Prime k-tuple|prime {{tmath|k}}-tuples]], patterns in the differences among more than two prime numbers. Their infinitude and density are the subject of the [[first Hardy–Littlewood conjecture]], which can be motivated by the [[heuristic]] that the prime numbers behave similarly to a random sequence of numbers with density given by the prime number theorem.<ref>{{harvnb|Ribenboim|2004}}, Prime {{tmath|k}}-tuples conjecture, pp. 201–202.</ref>