Factorial Divisible by Prime Power

Theorem

Let $n \in \Z: n \ge 1$.

Let $p$ be a prime number.

Let $n$ be expressed in base $p$ notation:

$\displaystyle n = \sum_{j=0}^m r_j p^j$

where $0 \le r_j < p$.

Let $n!$ be the factorial of $n$.

Let $p^\mu$ be the largest power of $p$ which divides $n!$, that is:

• $p^\mu \backslash n$
• $p^{\mu+1} \nmid n$

Then:

$\displaystyle \mu = \frac {n - s_p \left({n}\right)} {p-1}$

where $s_p \left({n}\right)$ is the digit sum of $n$.

Proof

If $p > n$, then $s_p \left({n}\right) = n$ and we have that:

$\displaystyle \frac {n - s_p \left({n}\right)} {p-1} = 0$

which ties in with the fact that $\displaystyle \left \lfloor{\frac n p}\right \rfloor = 0$.

Hence the result holds for $p > n$.

So, let $p \le n$.

From Multiplicity of Prime Factor in Factorial, we have that:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \mu\)	\(=\)	\(\displaystyle \sum_{k > 0} \left \lfloor{\frac n {p^k} }\right \rfloor\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left \lfloor{\frac n p}\right \rfloor + \left \lfloor{\frac n {p^2} }\right \rfloor + \left \lfloor{\frac n {p^3} }\right \rfloor + \cdots + \left \lfloor{\frac n {p^s} }\right \rfloor\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

where $p^s < n < p^{s+1}$.

From Quotient and Remainder to Number Base, we have that:

$\displaystyle \left \lfloor{\frac n {p^k}}\right \rfloor = \left[{r_m r_{m-1} \ldots r_{k+1} r_k}\right]_p = \sum_{j=0}^{m-k} r_j p^j$

where $0 \le r_j < p$.

Hence:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \mu\)	\(=\)	\(\displaystyle \sum_{k > 0} \left({\sum_{j=0}^{m-k} r_j p^j}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle r_m p^{m-1} + r_{m-1} p^{m-2} + \cdots + r_2 p + r_1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(+\)	\(\displaystyle r_m p^{m-2} + r_{m-1} p^{m-3} + \cdots + r_2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(+\)	\(\displaystyle \cdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(+\)	\(\displaystyle r_m p + r_{m-1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(+\)	\(\displaystyle r_m\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle r_m \sum_{j=0}^{m-1} p^j + r_{m-1} \sum_{j=0}^{m-2} p^j + \cdots + r_2 \sum_{j=0}^1 p^j + r_1 \sum_{j=0}^0 p^j\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{k=1}^m \left({r_k \sum_{j=0}^{k-1} p^j}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{k=1}^m \left({r_k \frac {p^k - 1}{p-1} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	from Sum of Geometric Progression
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac 1 {p-1} \left({\sum_{k=1}^m r_k p^k - \sum_{k=1}^m r_k}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Hence the result.

$\blacksquare$

History

This result is due to Adrien-Marie Legendre, who published it in Essai sur la Théorie des Nombres (2nd edition) in 1808.