Multiplicity of Prime Factor in Factorial

From ProofWiki
Jump to: navigation, search


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 \mathop > 0} \left \lfloor{\frac n {p^k}}\right \rfloor$

where $\left \lfloor{\cdot}\right \rfloor$ denotes the Floor Function.


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!$.


$\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.