the prime power dividing a factorial
In 1808, Legendre showed that the exact power of a prime dividing is
where is the largest power of being .
Proof.
If then doesn’t divide , and its power is 0, and the sumabove isempty. So let the prime .
For each , there are numbers between 1 and with being the greatest power of dividing each. So the power of dividing is
But each in thesum appears with factors and , so the above sum equals
∎
Corollary.
where denotes the sums of digits function in base .
Proof.
If , then and is . So we assume .
Let be the -adic representation of . Then
∎