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.
Why is n a lower bound for that product?
Each number from 1 to
has a unique factorization into a product of that form with each factor less than or equal to 
, and we counted all possible such products where the two factors are less than or equal to 
. It’s a lower bound because we actually counted too many such products. For example, if 
, we counted the product 
, even though this does not correspond to the factorization of any number less than or equal to 
.
Ah, thanks. I missed that we were counting factorizations of numbers <= n and not just of n.
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.
I left out 1=4/2^2, but 1 is also a square.
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.
Try to prove that $\sum_{i = 1}^{\infty}$ = $\infty$ diverges .