|
|
|
|
the prime power dividing a factorial
|
(Theorem)
|
|
|
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\rfloor$$ 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.$$ 
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.
|
|
(view preamble | get metadata)
Cross-references: representation, base, function, digits, numbers, sum, divide, prime
This is version 7 of the prime power dividing a factorial, born on 2003-01-20, modified 2003-10-10.
Object id is 3908, canonical name is PrimePowerDividingAFactorial.
Accessed 4396 times total.
Classification:
| AMS MSC: | 11A51 (Number theory :: Elementary number theory :: Factorization; primality) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|