There are Infinitely Many Primes (Erdős)

Problem: Prove there are infinitely many primes

Solution: Denote by \pi(n) the number of primes less than or equal to n. We will give a lower bound on \pi(n) which increases without bound as n \to \infty.

Note that every number n can be factored as the product of a square free number r (a number which no square divides) and a square s^2. In particular, to find s^2 recognize that 1 is a square dividing n, and there are finitely many squares dividing n. So there must be a largest one, and then r = n/s^2. We will give a bound on the number of such products rs^2 which are less than or equal to n.

If we want to count the number of square-free numbers less than n, we can observe that each square free number is a product of distinct primes, and so (as in our false proof that there are finitely many primes) each square-free number corresponds to a subset of primes. At worst, we can allow these primes to be as large as n (for example, if n itself is prime), so there are no more than 2^{\pi(n)} such subsets.

Similarly, there are at most \sqrt{n} square numbers less than n, since if x > \sqrt{n} then x^2 > n.

At worst the two numbers r, s^2 will be unrelated, so the total number of factorizations rs^2 is at most the product 2^{\pi(n)}\sqrt{n}. In other words,

2^{\pi(n)}\sqrt{n} \geq n

The rest is algebra: divide by \sqrt{n} and take logarithms to see that \pi(n) \geq \frac{1}{2} \log(n). Since \log(n) is unbounded as n grows, so must \pi(n). Hence, there are infinitely many primes.

Discussion: This is a classic analytical argument originally discovered by Paul Erdős. One of the classical ways to investigate the properties of prime numbers is to try to estimate \pi(n). In fact, much of the work of the famous number theorists of the past involved giving good approximations of \pi(n) in terms of logarithms. This usually involved finding good upper bounds and lower bounds and limits. Erdős’s proof is entirely in this spirit, although there are much closer and more accurate lower and upper bounds. In this proof we include a lot of values which are not actually valid factorizations (many larger choices of r, s^2 will have their product larger than n). But for the purposes of proving there are infinitely many primes, this bound is about as elegant as one can find.

About these ads

6 thoughts on “There are Infinitely Many Primes (Erdős)

    • Each number from 1 to n has a unique factorization into a product of that form with each factor less than or equal to n, and we counted all possible such products where the two factors are less than or equal to n. It’s a lower bound because we actually counted too many such products. For example, if n = 9, we counted the product 7*2^2, even though this does not correspond to the factorization of any number less than or equal to n.

  1. I must be missing something.

    r=n/s^2, where r is square-free does not seem to hold for n=4. Either 4=4/1^2, or 2=4/sqrt(2)^2. But I assume r, n, and s are positive integers, and n>=2. Or perhaps 1 is considered to be a square only when required?

    Still, I don’t see that this affects the result.

    • For the purposes of making these results more elegant, 1 is the exception and is not considered to be a square. The definition would not make sense otherwise: 1 is a square that divides all numbers, so there would be no square-free numbers.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s