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\lfloor \frac{n}{p^i}\rfloor$$

where $K$ is the largest power of $p$ being $\le 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 $\lfloor \frac{n}{p^i}\rfloor -\lfloor \frac{n}{p^{i+1}}\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(\lfloor \frac{n}{p^i}\rfloor -\lfloor \frac{n}{p^{i+1}}\rfloor \right).$$

But each $\lfloor \frac{n}{p^i}\rfloor ,i\ge 2$ in the sum appears with factors $i$ and $i-1$, so the above sum equals

$$\sum i=1^K\lfloor \frac{n}{p^i}\rfloor .$$

∎

Corollary.

$$\sum _{k=1}^K\lfloor \frac{n}{p^K}\rfloor =\frac{n-{\delta }_p(n)}{p-1},$$

where ${\delta }_p$ denotes the sums of digits function in base $p$.

Proof.

If , then ${\delta }_p(n)=n$ and $\lfloor \frac{n}{p}\rfloor$ is $0=\frac{n-{\delta }_p(n)}{p-1}$. So we assume $p\le n$.

Let $n_K{n}_{K-1}\mathrm{\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({\displaystyle \sum _{j=0}^{k-1}}{p}^j\right)$

$=\left(n_1+n_{2}p+\mathrm{\dots }+n_K{p}^{K-1}\right)$

$+\left(n_2+n_{3}p+\mathrm{\dots }+n_K{p}^{K-2}\right)$

$\mathrm{\ddots }$

$+n_K$

$={\displaystyle \sum _{k=1}^K}\lfloor {\displaystyle \frac{n}{p^k}}\rfloor .$

∎

Title	the prime power dividing a factorial
Canonical name	ThePrimePowerDividingAFactorial
Date of creation	2013-03-22 13:22:34
Last modified on	2013-03-22 13:22:34
Owner	Thomas Heye (1234)
Last modified by	Thomas Heye (1234)
Numerical id	10
Author	Thomas Heye (1234)
Entry type	Theorem
Classification	msc 11A51