proof of infinitude of primes

We begin by noting a fact about factorizations. Suppose that n>0 is an integer which has a prime factorizationMathworldPlanetmath


Then, because 2 is the smallest prime numberMathworldPlanetmath, we must have


so n2k1+k2++km.

Assume that there were only a finite number of prime numbers p1,p2,pm. By the above-noted fact, given a positive integer j, every integer n such that 2jn>0 could be expressed as




This, however, leads to a contradictionMathworldPlanetmathPlanetmath because it would imply that there exist more integers than possible factorizations despite the fact that every integer is supposed to have a prime factorization. To see this, let us over-count the number of factorizations. A factorization being specified by an m-tuplet of integers k1,k2,,kn such that k1+k2++kmj, the number of factorizations is equal to the number of such tuplets. Now, for all i we must have 0kij, so there are not more than (j+1)m such tuplets available. However, for all m, one can choose j such that 2j>jm. For such a choice of j we could not make ends meet — there are not enough possible factorizations available to handle all integers, so we conclude that there must be more than m primes for any integer m, i.e. that the number of primes is infiniteMathworldPlanetmath.

To make this exposition self-contained, we conclude with a proof that, for every m, there exists a j such that 2j>(j+1)m. We begin by showing that, for every integer a1, we have 2a>a. This is an easy inductionMathworldPlanetmath. When a=1, we have 21=2>1. If 2a>a for some a>1, then 2a+1=2a+2a>a+a>a+1. Hence, by induction, 2a>a for all a1.

From this starting point, we obtain the desired inequality by algebraic manipulation. Suppose that a>2. Multiplying both sides by 2, we get 2a+1>2a>a+2. Setting a=m-2, we have 2m-1>m, or 2m>2m. Raising both sides to the 2m-th power, 22m2>22mm2m=2m(2m2)m2(2m2)m. Setting j=(2m2-1), this becomes 2j>(j+1)2.

Title proof of infinitude of primes
Canonical name ProofOfInfinitudeOfPrimes
Date of creation 2013-12-27 17:11:49
Last modified on 2013-12-27 17:11:49
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 15
Author rspuzio (6075)
Entry type Proof
Classification msc 11A41