# 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 \mathop > 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 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$

## Sources

- Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(1968): $\S 1.2.5 \ (8)$ - P.M. Cohn:
*Algebra Volume 1*(2nd ed., 1982)... (previous)... (next): $\S 2.2$: Divisibility and factorization in $\mathbf Z$: Exercise $5$ - James S. Kraft and Lawrence C. Washington:
*An Introduction to Number Theory with Cryptography*(2013): $\S 3.6$