Euclid's theorem
Euclid offered a proof published in his work Elements (Book IX, Proposition 20),[1] which is paraphrased here.
[2] Consider any finite list of prime numbers p1, p2, ..., pn.
It will be shown that there exists at least one additional prime number not included in this list.
Let P be the product of all the prime numbers in the list: P = p1p2...pn.
[4] In the original work, Euclid denoted the arbitrary finite set of prime numbers as A, B, Γ.
[5] Euclid is often erroneously reported to have proved this result by contradiction beginning with the assumption that the finite set initially considered contains all prime numbers,[6] though it is actually a proof by cases, a direct proof method.
However, since this assumption isn't even used in the proof, the reformulation is pointless.
"[7] Several variations on Euclid's proof exist, including the following: The factorial n!
[8] Another proof, by the Swiss mathematician Leonhard Euler, relies on the fundamental theorem of arithmetic: that every integer has a unique prime factorization.
What Euler wrote (not with this modern notation and, unlike modern standards, not restricting the arguments in sums and products to any finite sets of integers) is equivalent to the statement that we have[9]
In the penultimate sum, every product of primes appears exactly once, so the last equality is true by the fundamental theorem of arithmetic.
In his first corollary to this result Euler denotes by a symbol similar to
the "absolute infinity" and writes that the infinite sum in the statement equals the "value"
, to which the infinite product is thus also equal (in modern terminology this is equivalent to saying that the partial sum up to
is divergent, where P denotes the set of all prime numbers (Euler writes that the infinite sum equals
Paul Erdős gave a proof[11] that also relies on the fundamental theorem of arithmetic.
In the 1950s, Hillel Furstenberg introduced a proof by contradiction using point-set topology.
, called the evenly spaced integer topology, by declaring a subset
Then by the inclusion–exclusion principle, the number of positive integers less than or equal to x that are divisible by one of those primes is
In 2010, Junho Peter Whang published the following proof by contradiction.
(the numerator of the fraction would grow singly exponentially while by Stirling's approximation the denominator grows more quickly than singly exponentially), contradicting the fact that for each k the numerator is greater than or equal to the denominator.
Filip Saidak gave the following proof by construction, which does not use reductio ad absurdum[15] or Euclid's lemma (that if a prime p divides ab then it must divide a or b).
So the chain of pronic numbers:1×2 = 2 {2}, 2×3 = 6 {2, 3}, 6×7 = 42 {2, 3, 7}, 42×43 = 1806 {2, 3, 7, 43}, 1806×1807 = 3263442 {2, 3, 7, 43, 13, 139}, · · ·provides a sequence of unlimited growing sets of primes.
By the fundamental theorem of arithmetic, any positive integer n could then be represented as
where the non-negative integer exponents ei together with the finite-sized list of primes are enough to reconstruct the number.
This is a much more efficient encoding than representing n directly in binary, which takes
and note that by assumption all positive integers relatively prime to it are in the set
In other words, there are infinitely many primes that are congruent to a modulo d. Let π(x) be the prime-counting function that gives the number of primes less than or equal to x, for any real number x.
The prime number theorem then states that x / log x is a good approximation to π(x), in the sense that the limit of the quotient of the two functions π(x) and x / log x as x increases without bound is 1:
In number theory, Bertrand's postulate is a theorem stating that for any integer
