Understanding Legendre's Formula

Suppose we want to find how many times 3 divides 28!. Let's say by expanding 28!:

$$(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)(17)(18)(19)(20)(21)(22)(23)(24)(25)(26)(27)(28)$$

There are in total \(\lfloor \frac{n}{a} \rfloor\) multiples of \(a\) below \(n\), meaning there are \(\lfloor \frac{28}{3} \rfloor\) multiples of 3 below 28.

$$ \left \lfloor \frac{28}{3} \right \rfloor = 9$$

There are 9 numbers below 28 that are multiples of 3, which means there are 9 numbers in 28! which can be divided by 3:

$$ \frac{(1)(2)(\textcolor{red}{3})(4)(5)(\textcolor{red}{6})(7)(8)(\textcolor{red}{9})(10)(11)(\textcolor{red}{12})(13)(14)(\textcolor{red}{15})(16)(17)(\textcolor{red}{18})(19)(20)(\textcolor{red}{21})(22)(23)(\textcolor{red}{24})(25)(26)(\textcolor{red}{27})(28)}{3^9} $$$$ (1)(2)(\textcolor{red}{1})(4)(5)(\textcolor{red}{2})(7)(8)(\textcolor{red}{3})(10)(11)(\textcolor{red}{4})(13)(14)(\textcolor{red}{5})(16)(17)(\textcolor{red}{6})(19)(20)(\textcolor{red}{7})(22)(23)(\textcolor{red}{8})(25)(26)(\textcolor{red}{9})(28) $$

Looking at the numbers above, you can see that there are some numbers which can be divided by 3 again. There are in total \(\lfloor \frac{28}{3^2} \rfloor\) (or 3) numbers below 28 that can be divided by 3 twice:

$$ \frac{(1)(2)(1)(4)(5)(2)(7)(8)(\textcolor{red}{3})(10)(11)(4)(13)(14)(5)(16)(17)(\textcolor{red}{6})(19)(20)(7)(22)(23)(8)(25)(26)(\textcolor{red}{9})(28)}{3^3} $$$$ (1)(2)(1)(4)(5)(2)(7)(8)(\textcolor{red}{1})(10)(11)(4)(13)(14)(5)(16)(17)(\textcolor{red}{2})(19)(20)(7)(22)(23)(8)(25)(26)(\textcolor{red}{3})(28) $$

Now there are in total \(\lfloor \frac{28}{3^3} \rfloor\) (or 1) number below 28 that can be divided by 3 a third time:

$$ \frac{(1)(2)(1)(4)(5)(2)(7)(8)(1)(10)(11)(4)(13)(14)(5)(16)(17)(2)(19)(20)(7)(22)(23)(8)(25)(26)(\textcolor{red}{3})(28)}{3^1} $$$$ (1)(2)(1)(4)(5)(2)(7)(8)(1)(10)(11)(4)(13)(14)(5)(16)(17)(2)(19)(20)(7)(22)(23)(8)(25)(26)(\textcolor{red}{1})(28) $$

Since \(\lfloor \frac{28}{3^4} \rfloor = 0\), then there are no numbers below 28 that can be divided by 3 four or more times. For the final number we calculated, if we take it's prime factorization, there would be no 3's because we have divided it all. This means 3 can divide 28 in total \(\lfloor \frac{28}{3^1} \rfloor + \lfloor \frac{28}{3^2} \rfloor + \lfloor \frac{28}{3^3} \rfloor \) = 13 times. Similarly, 5 can divide 28! in total \(\lfloor \frac{28}{5^1} \rfloor + \lfloor \frac{28}{5^2} \rfloor + \lfloor \frac{28}{5^3} \rfloor \ldots =\) 6 times. We can generalize this and say that prime \(p\) divides \(n!\) in total \(e\) times, where \(e\) is:

$$\left \lfloor \frac{n}{p} \right \rfloor + \left \lfloor \frac{n}{p^2} \right \rfloor + \left \lfloor \frac{n}{p^3} \right \rfloor \ldots$$

In other words the largest power of prime \(p\) that can divide \(n!\) is \(e\). Keep in mind this method only works with prime numbers. If we want to know how many times 4 divides 6! (or 720, we can manually check that it's 2 times, but \(\lfloor \frac{6}{4} \rfloor + \lfloor \frac{6}{4^2} \rfloor \ldots \) is 1. If we expand 6!, we see that there is only one number that can be divided by 4:

$$ (1)(2)(3)(\textcolor{red}{4})(5)(6) $$

Although 4 can only divide 4, 2 can divide both 2 and 6. This means 720 can be divided by 4 once and 2 twice, but Legendre's formula only considers that one 4 and not the two 2's.