GBB Services  
GBB Services : Resources : Mathematics : Prime numbers 
There are infinitely many primesby Walter VanniniStarting Point Euclid's counter example Kummer's counter example Other counter examples Euler's analytic proof Thue's counting proof Chaitin's algorithmic complexity proof Erdos' counting proof Concluding words Feedback IntroductionThe first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, … They're defined as the positive integers that have exactly two positive integer factors (which are themselves and one, of course). One of the oldest significant mathematical results is that there's an infinite number of primes. It was first proved by Euclid in about 300 BC, in his Elements (book IX, proposition 20). Over the years, many different proofs of the result have been found. Six of them can be found in Chapter 1 of the third edition of "Proofs from THE BOOK". Three can be found in Chapter 2 of Hardy and Wright's "An Introduction to the Theory of Numbers" (in sections 2.1, 2.4, and 2.6). Three can be found in Chapter 2 of Chaitin's "Meta Math!". Several can be found in the wikipedia primes entry. For quite a while, I knew of only one proof of the "infinitude of primes", namely Euclid's proof. Over the years, I've come across others, and I've noticed that several of them are really relying on deriving a contradiction from a particular consequence of assuming that there are finitely many primes. That consequence, and various ways of disproving it, are the subject of this essay. I might deal with some of the other proofs in the future. Starting pointAssume there are only finitely many primes. Call them 2, 3, 5, … p_{k}Since every positive integer, other than one, is either itself prime, or a product of primes, we can conclude that every positive integer N can be written in the form N = 2^{n1} 3^{n2} 5^{n3} … p_{k}^{nk}where each of n_{1}, n_{2}, n_{3}, … n_{k} is a nonnegative integer. All of the proofs discussed here will show, in one way or another, that this is impossible. Euclid's counter exampleEuclid's proof that not every integer is of the form 2^{n1} 3^{n2} 5^{n3} … p_{k}^{nk}is very direct. He simply pointed out that the number N = 2 • 3 • 5 • … • p_{k} + 1can't be of the required form. Kummer's counter exampleIn 1878, Kummer pointed out that the number N = 2 • 3 • 5 • … • p_{k} − 1can't be of the required form either. Other counter examplesAnd, of course, there's an infinite number of related counter examples. All numbers of the form N = n • 2 • 3 • 5 • … • p_{k} ± 1where n is any positive integer, provide a counter example also. Unlike Euclid's (and Kummer's) proof, all the remaining proofs won't produce an explicit counter example. Euler's analytic proofWhat I really like about the following proof is that it uses techniques from another area of mathematics, real analysis, to give a short and sweet proof involving infinite sums and convergence. It is true that the proof could be reformulated in terms of inequalities involving finite sums of rational numbers (and from there could be restated purely in terms of finite operations on integers) but it would lose its conceptual simplicity in the process. Euler's great insight, in my opinion, was to realize that if every number is of the given form, then it would follow that a finite product of convergent geometric series would be equal to the harmonic series. This is impossible because the harmonic series diverges. Here's some details. By considering all terms resulting from expanding the following product, we have: (1 + 1/2 + 1/2^{2} + 1/2^{3} + … )(1 + 1/3 + 1/3^{2} + 1/3^{3} + … ) (1 + 1/5 + 1/5^{2} + 1/5^{3} + … ) … (1 + 1/p_{k} + 1/p_{k}^{2} + 1/p_{k}^{3} + … ) ≥ (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + … ) We only need inequality, which is just as well, since proving equality would require proving that prime factorization is unique, which is something we don't need for any of the proofs. Now, since every prime is ≥ 2, we have that every geometric series in the above product is bounded above by (1 + 1/2 + 1/2^{2} + 1/2^{3} + … ) = 2This immediately implies the inequality 2^{k} ≥ (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + … )Since (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + … ) = ∞ , we're done. Another way to think of the result is that Euler showed that the sum of the reciprocals of all numbers of the form 2^{n1} 3^{n2} 5^{n3} … p_{k}^{nk}is finite, while the sum of the reciprocals of all positive integers is infinite. This can be interpreted to mean that for any collection of primes, "most" positive integers are not products of only those primes. Thue's counting proofLike Euler's proof, this proof shows that there must be positive integers that are not of the required form. But, we don't leave the realm of the integers. This proof starts by looking at the set of integers ranging from 1 up to 2^{n}. The cardinality of this set is 2^{n}. On the other hand, by the finiteness assumption, every integer from 1 to 2^{n} can be written in the form 2^{n1} 3^{n2} 5^{n3} … p_{k}^{nk}where each of n_{1}, n_{2}, n_{3}, … n_{k} ranges from 0 to n. The cardinality of this set is (n+1)^{k}. This means that we must have the inequality 2^{n} ≤ (n+1)^{k} for all n.But this is known to be false for sufficiently large n. This proof shows that the infinitude of primes follows from the fact that exponential growth out paces polynomial growth. Chaitin's algorithmic complexity proofThe informal version of Gregory Chaitin's proof can be found in his book "Meta Math!". In short, it takes log N bits of information to represent a "random" integer N, but it only takes k log log N bits to represent N if it's of the form 2^{n1} 3^{n2} 5^{n3} … p_{k}^{nk}Since log N grows faster than log log N we're done. When I read this, I thought it would be amusing to restate it as a simple counting argument, and quickly did so: just write N as 2^{n}, so that log N is log(2^{n}), and k log log N is log(n^{k}), and follow your nose. You'll get Thue's proof. After that, I thought I'd look at Chaitin's original published proof. It appeared as "Appendix 2: An InformationTheoretic Proof That There Are Infinitely Many Primes" in his 1979 paper Toward a mathematical definition of "life". In that paper, Chaitin defines algorithmic entropy H of a positive integer N, and uses various properties, such as "subadditivity of algorithmic entropy" to show that H(N) ≤ Sum( H(n_{j}) ) + O(1), from which it follows that log N + O(log log N) ≤ k[log log N + O(log log log N)];which gives the the contradiction log N = O(log log N). The final paragraph of the paper reads as follows "This proof is merely a formalization of the observation that if there were only finitely many primes, the prime factorization of a number would usually be a much more compact representation for it than its basetwo numeral, which is absurd. This proof appears, formulated as a counting argument, in Section 2.6 of the 1938 edition of Hardy and Wright [20]; we believe that it is also quite natural to present it in an informationtheoretic setting." (italics mine). I looked in Hardy and Wright, expecting to see Thue's proof, and was pleasantly surprised to find that Chaitin referenced a different counting argument, due to Erdos. Erdos' counting proofLook at the set of integers ranging from 1 up to 2^{2n}. The cardinality of this set is 2^{2n}. By the finiteness assumption, every integer from 1 to 2^{2n} can be written in the form 2^{n1} 3^{n2} 5^{n3} … p_{k}^{nk}Erdos used the fact that n_{i}=2m_{i}+e_{i} where e_{i} is 0 or 1 (so that p_{i}^{ni}=(p_{i}^{mi})^{2}p_{i}^{ei}) to conclude that every integer from 1 to 2^{2n} can be written as M^{2} 2^{e1} 3^{e2} 5^{e3} … p_{k}^{ek}where M ranges from 1 to 2^{n}, and each of e_{1}, e_{2}, e_{3}, … e_{k} ranges from 0 to 1. The cardinality of this set is 2^{n} 2^{k}. This means that we must have the inequality 2^{2n} ≤ 2^{n}2^{k}, ie 2^{n} ≤ 2^{k} for all n. But this is clearly false: just take n=k+1. Incidentally, there's nothing special about the 2 in either the base or exponent of 2^{2n}: any integers greater that 1 would also work. Here's how the argument would go with a base of 42 and with a factor of 1729 in the exponent. Look at the set of integers ranging from 1 up to 42^{1729n}. The cardinality of this set is 42^{1729n}. By the finiteness assumption, every integer from 1 to 42^{1729n} can be written in the form 2^{n1} 3^{n2} 5^{n3} … p_{k}^{nk}Use the fact that n_{i}=1729m_{i}+e_{i} where e_{i} is 0 or 1 or ... or 1728 (so that p_{i}^{ni}=(p_{i}^{mi})^{1729}p_{i}^{ei}) to conclude that every integer from 1 to 42^{1729n} can be written as M^{1729} 2^{e1} 3^{e2} 5^{e3} … p_{k}^{ek}where M ranges from 1 to 42^{n}, and each of e_{1}, e_{2}, e_{3}, … e_{k} ranges from 0 to 1728. The cardinality of this set is 42^{n} 1729^{k}. This means that we must have the inequality 42^{1729n} ≤ 42^{n}1729^{k}, ie 42^{1728n} ≤ 1729^{k} for all n. But this is clearly false: just take n large enough. On the other hand, the 2 in the base of 2^{n} in Thue's proof has to be 2. We're relying on the fact that every prime is greater than or equal to 2. Concluding wordsWe've looked at only one approach to proving that there are infinitely many primes. There are several others, including yet another proof due to Euler, in which he showed that the sum of the reciprocals of the primes is infinite. It turns out that the idea behind Erdos' counting proof can be used to give an alternative proof of Euler's sum of the reciprocals of primes result, and this is just what Erdos did. If you're curious, you can read about it in either Proofs from THE BOOK or in Hardy and Wright's classic number theory book. FeedbackJohn Stillwell sent me an email asking "Have you looked at Ribenboim's Little Book of Bigger Primes ?". Err, no, I hadn't. I checked it out, and found out that Thue's name is associated with the counting version of Chaitin's proof, and that Kummer's name was associated with a variation of Euclid's proof. No mention of Erdos' counting argument though. I've modified this essay accordingly. If you have corrections, additions, modifications, etc please let me know mailto:walterv@gbbservices.com
