Login
This is a place holder for potential sponsor logos.
the prime power dividing a factorial
In 1808, Legendre showed that the exact power of a prime $p$ dividing $n!$ is$$\sum_{i=1}^K \left\lfloor \frac{n}{p^i} \right\rfloo$$ where $K$ is the largest power of $p$ being $\leq n$ .
Proof. If $p>n$ then $p$ doesn't divide $n!$ , and its power is 0, and the sum above is empty. So let the prime $p \le n$ .
For each $1 \le i \le K$ , there are $\left\lfloor \frac{n}{p^i} \right\rfloor -\left\lfloor \frac{n}{p^{i+1}} \right\rfloor$ numbers between 1 and $n$ with $i$ being the greatest power of $p$ dividing each. So the power of $p$ dividing $n!$ is$$\sum_{i=1}^K i\cdot \left(\left\lfloor \frac{n}{p^i} \right\rfloor -\left\lfloor \frac{n}{p^{i+1}} \right\rfloor\right)$$ But each $\left\lfloor \frac{n}{p^i} \right\rfloor, i \ge 2$ in the sum appears with factors $i$ and $i-1$ , so the above sum equals$$\sum{i=1}^K \left\lfloor \frac{n}{p^i} \right\rfloor$$
For each $1 \le i \le K$ , there are $\left\lfloor \frac{n}{p^i} \right\rfloor -\left\lfloor \frac{n}{p^{i+1}} \right\rfloor$ numbers between 1 and $n$ with $i$ being the greatest power of $p$ dividing each. So the power of $p$ dividing $n!$ is$$\sum_{i=1}^K i\cdot \left(\left\lfloor \frac{n}{p^i} \right\rfloor -\left\lfloor \frac{n}{p^{i+1}} \right\rfloor\right)$$ But each $\left\lfloor \frac{n}{p^i} \right\rfloor, i \ge 2$ in the sum appears with factors $i$ and $i-1$ , so the above sum equals$$\sum{i=1}^K \left\lfloor \frac{n}{p^i} \right\rfloor$$
Corollary 1 $$\sum_{k=1}^K \left\lfloor \frac{n}{p^K} \right\rfloor =\frac{n -\delta_p(n)}{p-1}$$ where $\delta_p$ denotes the sums of digits function in base $p$ .
Proof. If $n < p$ , then $\delta_p(n) =n$ and $\left\lfloor \frac{n}{p} \right\rfloor$ is $0 =\frac{n -\delta_p(n)}{p-1}$ . So we assume $p \leq n$ .
Let $n_Kn_{K-1}\cdots n_0$ be the $p$ -adic representation of $n$ . Then \begin{eqnarray*} \frac{n -\delta_p(n)}{p-1} &= \sum_{k=1}^K n_k\left(\sum_{j=0}^{k-1} p^j\right) \\ &=\sum_{0 \le j < k \le K} p^j.n_k \\ &=\left(n_1 +n_2p +\ldots +n_Kp^{K-1}\right) \\ &+\left(n_2 +n_3p +\ldots +n_Kp^{K-2}\right) \\ & \ddots \\ & +n_K \\ &&= \sum_{k=1}^K \left\lfloor \frac{n}{p^k}\right\rfloor. \end{eqnarray*} 
the prime power dividing a factorial is owned by Thomas Heye.
None.
[ View all 1 ]