# The factorials are too damn high!

Suppose I want to know how many factors of $2$ are in $n!$, for some $n$. How would I go about computing that? For each even number less than or equal to $n$, I get at least one factor of $2$ in $n!$. So The number of factors is at least $\lfloor\frac n2\rfloor$. But there’s more. For the numbers divisible by $4$, I only counted one copy of $2$. I need to count another for each multiple of $4$. There are $\lfloor \frac n4\rfloor$ multiples of $4$ less than or equal to $n$. But then multiples of $8$, $16$, etc.

Let $D_p(n)$ denote the number of factors of some prime $p$ in $n!$. The above argument generalizes to show that

$D_p(n)=\lfloor\frac np\rfloor+\lfloor\frac n{p^2}\rfloor+\lfloor\frac n{p^3}\rfloor+\cdots$

Taking the floor of each term in the sum only makes things smaller, so we have the inequality:

$D_p(n)\le \frac np+\frac n{p^2}+\frac n{p^3}+\cdots=n\cdot\left(\frac 1{p-1}\right)$

Now suppose there were only finitely many primes. We can factor

$n!=\prod_{i=1}^rp_i^{D_{p_i}(n)}$

We’re about to do some work with the exponents, so let’s take the log of everything in sight to make this notationally easier:

$\log n!=\sum_{i=1}^r D_{p_i}(n)\cdot \log p_i$.

Now using our inequality from before,

$\log n! \le n\cdot\sum_{i=1}^r\left(\frac1{p_i-1}\right)\cdot\log p_i$

I don’t particularly care what that sum is, but I do care that it’s some fixed number, independent of $n$. If there were infinitely many primes, it would be an infinite sum that doesn’t converge, making the inequality say that $\log n!\le \infty$, which is useless. But under the assumption that there are only finitely many primes, we know that there is some fixed constant $c$ (that sum) for which $\log n!$ is never larger than $c\cdot n$. What this means is that $n!\le c^n$ always. This is just not true. If $n>c$, then increasing $n$ makes $n!$ grow faster than $c^n$. More than that, how much faster is unbounded.

I don’t really want to go into the details here, but it should be believable that factorials grow faster than any exponential. That is, if you give me a constant $c$, I can give you a number $N$ such that $N!>c^N$. To see exactly how fast they grow, have a look at Stirling’s approximation. Anyway, if there were finitely many primes, factorials wouldn’t be able to grow as fast as they should, so we have a contradiction. That is, there are infinitely many primes.