We denote the product of the first \(20\) natural numbers by \(20!\) and call this \(20\) factorial.
- 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!\).
- 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?
- 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!
