Multiplicity of Prime Factor in Factorial
Theorem
Let $n!$ be the factorial of $n$.
Let $p$ be a prime number.
Then $p^\mu$ is a divisor of $n!$, and $p^{\mu + 1}$ is not, where:
- $\displaystyle \mu = \sum_{k > 0} \left \lfloor{\frac n {p^k}}\right \rfloor$
where $\left \lfloor{\cdot}\right \rfloor$ denotes the Floor Function.
Proof
Note that although the summation given in the statement of the theorem is given as an infinite sum, in fact it terminates after a finite number of terms (because when $p^k > n$ we have $0 < n/p^k < 1$).
From Number of Multiples Less Than a Given Number, we have that $\left \lfloor{\dfrac n {p^k}}\right \rfloor$ is the number of integers $m$ such that $0 < m \le n$ which are multiples of $p^k$.
We look more closely at $n!$:
- $n! = 1 \times 2 \times \ldots \times \left({n-1}\right) \times n$
We see that any integer $m$ such that $0 < m \le n$ which is divisible by $p^j$ and not $p^{j+1}$ must be counted exactly $j$ times.
That is: once in $\left \lfloor{\dfrac n p}\right \rfloor$, once in $\left \lfloor{\dfrac n {p^2}}\right \rfloor$, $\ldots$, once in $\left \lfloor{\dfrac n {p^j}}\right \rfloor$.
And that is all the occurrences of $p$ as a factor of $n!$.
Thus:
- $\displaystyle \mu = \left \lfloor{\frac n p}\right \rfloor + \left \lfloor{\frac n {p^2}}\right \rfloor + \cdots + \left \lfloor{\frac n {p^j}}\right \rfloor$
Hence the result.
$\blacksquare$
