Editing Prime number (section)

=== 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.