# 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\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\leq n$.
For each $1\leq i\leq 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\geq 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.
 $\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, 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_{K}n_{K-1}\cdots n_{0}$ be the $p$-adic representation of $n$. Then

 $\displaystyle\frac{n-\delta_{p}(n)}{p-1}$ $\displaystyle=\sum_{k=1}^{K}n_{k}\left(\sum_{j=0}^{k-1}p^{j}\right)$ $\displaystyle=\sum_{0\leq j $\displaystyle=\left(n_{1}+n_{2}p+\ldots+n_{K}p^{K-1}\right)$ $\displaystyle+\left(n_{2}+n_{3}p+\ldots+n_{K}p^{K-2}\right)$ $\displaystyle\ddots$ $\displaystyle+n_{K}$ $\displaystyle=\sum_{k=1}^{K}\left\lfloor\frac{n}{p^{k}}\right\rfloor.$

Title the prime power dividing a factorial  ThePrimePowerDividingAFactorial 2013-03-22 13:22:34 2013-03-22 13:22:34 Thomas Heye (1234) Thomas Heye (1234) 10 Thomas Heye (1234) Theorem msc 11A51