Food for thought

## Solution

We denote the product of the first $20$ natural numbers by $20!$ and call this $20$ factorial.

1. What is the highest power of $5$ which is a divisor of $20$ factorial?

We have $20! = 20 \times 19 \times 18 \times \dotsm \times 3 \times 2 \times 1$.

Since $5$ is a prime number, we can just add the highest power of $5$ dividing each of the numbers $1$, $2$, $3$, …, $20$. This is $0$ for each number not divisible by $5$. There are only four numbers in this range ($5$, $10$, $15$, $20$) that are divisible by $5^1$, and none of them is divisible by $5^2$. So the highest power of $5$ dividing $20!$ is $5^4$.

Just how many factors does $20!$ have altogether?

The first thing we need to do is find the prime factorisation of $20!$. As $20!=20 \times 19 \times 18 \times \dotsm \times 3 \times 2 \times 1$, we can can do this by finding the prime factorisation of each of the numbers $2$, $3$, …, $20$ (ignoring $1$ since it won’t contribute any primes) and multiplying them together.

Number Prime factorisation
$2$ $2$
$3$ $3$
$4$ $2^2$
$5$ $5$
$6$ $2 \times 3$
$7$ $7$
$8$ $2^3$
$9$ $3^2$
$10$ $2 \times 5$
$11$ $11$
$12$ $2^2 \times 3$
$13$ $13$
$14$ $2 \times 7$
$15$ $3 \times 5$
$16$ $2^4$
$17$ $17$
$18$ $2 \times 3^2$
$19$ $19$
$20$ $2^2 \times 5$

Multiplying the prime factorisations in the right-hand column together and simplifying, we get $20!=2^{18} \times 3^8 \times 5^4 \times 7^2 \times 11 \times 13 \times 17 \times 19.$

Now we can use this to calculate the number of divisors of $20!$. Each divisor will have a unique prime factorisation, which must be ‘contained’ within the prime factorisation of $20!$. Let $m$ be a divisor of $20!$. Then there are nineteen possible values for the highest power of $2$ dividing $m$ ($0$, $1$, …, $18$). Similarly, there are nine possible values for the highest power of $3$ dividing $m$ ($0$, $1$, …, $8$). Continuing in this way for all the prime factors of $20!$, we can calculate that there are $19 \times 9 \times 5 \times 3 \times 2 \times 2 \times 2 \times 2 = 41040$ divisors of $20!$.

1. Show that the highest power of $p$ that divides $500!$, where $p$ is a prime number and $p^t<500 < p^{t+1}$, is $\lfloor 500/p\rfloor+\lfloor 500/p^2\rfloor+\dotsb+\lfloor 500/p^t\rfloor,$ where $\lfloor x\rfloor$ (the floor of $x$) means to round $x$ down to the nearest integer. (For example, $\lfloor 3\rfloor=3$, $\lfloor 4.7\rfloor=4$, $\lfloor -2.7\rfloor=-3$, and so on.)

We can see that $\lfloor 500/p\rfloor$ is the number of multiples of $p$ that are less than or equal to $500$. For example, if $p$ goes into $500$ “seven and a bit” times, this means that $p$, $2p$, …, $7p$ are less than $500$ but $8p$ is greater than $500$.

Similarly, $\lfloor 500/p^2\rfloor$ is the number of multiples of $p^2$ that are less than or equal to $500$, and so on.

Now, we can work out the highest power of $p$ that divides $500!$ by considering the number of multiples of $p$, $p^2$, …, $p^t$ less than $500$.

We need to count all the multiples of $p$. We need to count the multiples of $p^2$ twice, since they contribute $2$ to the exponent, but we have already counted them once as they are also multiples of $p$ so we need to count them just once more. Similarly, we need to count the multiples of $p^3$ three times in total, but we have already counted them twice (once in the multiples of $p$ and once in the multiples of $p^2$), so we need to count them just once more. And so on for the remaining powers. So the highest power of $p$ that divides $500!$ has exponent $\left\lfloor \frac{500}{p}\right\rfloor+\left\lfloor \frac{500}{p^2}\right\rfloor+ \dotsb +\left\lfloor \frac{500}{p^t}\right\rfloor$

Note that we had to assume that $p$ was prime. What would have gone wrong if it had not been?

1. How many factors does $n!$ have?

We can generalise the above result beyond the case of $500!$. The highest power of $p$ that divides $n!$, where $p^t \leq n < p^{t+1}$, is equal to $\left\lfloor \frac{n}{p}\right\rfloor + \left\lfloor \frac{n}{p^2}\right\rfloor + \dotsb + \left\lfloor \frac{n}{p^t}\right\rfloor,$ by exactly the same reasoning as in (b).

We can use this information to find the prime factorisation of $n!$. Let $P$ be the largest prime with $P\leq n$. Also, for any number $m$, let $t_m$ be the integer such that $m^{t_m} \leq n< m^{t_m+1}$.

Using the information from part (b), we can then calculate the prime factorisation of $n!$: we have \begin{align*} n! &= 2^{\left(\lfloor n/2\rfloor+\lfloor n/2^2\rfloor + \dotsb + \lfloor n/2^{t_2}\rfloor\right)} \times 3^{\left(\lfloor n/3\rfloor+\lfloor n/3^2\rfloor + \dotsb + \lfloor n/3^{t_3}\rfloor\right)} \times \dotsm\\ &\qquad\times P^{\left(\lfloor n/P\rfloor+\lfloor n/P^2\rfloor + \dotsb + \lfloor n/P^{t_P}\rfloor\right)}. \end{align*}

Then we can use the same reasoning as at the end of part (a) to calculate the number of factors of $n!$: we get

\begin{align*} &\left(1 + \left\lfloor \frac{n}{2}\right\rfloor+\left\lfloor \frac{n}{2^2}\right\rfloor+ \dotsb + \left\lfloor \frac{n}{2^{t_2}}\right\rfloor\right) \times \left(1 + \left\lfloor \frac{n}{3}\right\rfloor + \left\lfloor \frac{n}{3^2}\right\rfloor + \dotsb + \left\lfloor \frac{n}{3^{t_3}}\right\rfloor\right) \times \dotsm\\ &\qquad\times \left(1 + \left\lfloor \frac{n}{P}\right\rfloor + \left\lfloor \frac{n}{P^2}\right\rfloor + \dotsb +\left\lfloor \frac{n}{P^{t_P}}\right\rfloor\right). \end{align*}

We can check that this expression works for the example of $20!$:

\begin{align*} &\left(1 + \left\lfloor \frac{20}{2}\right\rfloor+\left\lfloor \frac{20}{4}\right\rfloor+\left\lfloor \frac{20}{8}\right\rfloor+\left\lfloor \frac{20}{16}\right\rfloor \right) \times \left(1 + \left\lfloor \frac{20}{3}\right\rfloor + \left\lfloor \frac{20}{9}\right\rfloor\right) \times \\ &\qquad \left(1 + \left\lfloor \frac{20}{5}\right\rfloor\right) \times \left(1 + \left\lfloor \frac{20}{7}\right\rfloor\right) \times \left(1 + \left\lfloor \frac{20}{11}\right\rfloor\right) \times \\ &\qquad \left(1 + \left\lfloor \frac{20}{13}\right\rfloor\right) \times \left(1 + \left\lfloor \frac{20}{17}\right\rfloor\right) \times \left(1 + \left\lfloor \frac{20}{19}\right\rfloor\right)\\ &\quad=(10+5+2+1+1) \times (6+2+1) \times (4+1) \times (2+1) \times\\ &\qquad (1+1) \times (1+1) \times (1+1) \times (1+1)\\ &\quad=19 \times 9 \times 5 \times 3 \times 2 \times 2 \times 2 \times 2\\ &\quad= 41040. \end{align*}

This is the same answer as in part (a), suggesting that this formula works!