the prime power dividing a factorial

In 1808, Legendre showed that the exact power of a prime p dividing n! is


where K is the largest power of p being n.


If p>n then p doesn’t divide n!, and its power is 0, and the sum above is empty. So let the prime pn.
For each 1iK, there are npi-npi+1 numbers between 1 and n with i being the greatest power of p dividing each. So the power of p dividing n! is


But each npi,i2 in the sum appears with factors i and i-1, so the above sum equals



where δp denotes the sums of digits function in base p.


If n<p, then δp(n)=n and np is 0=n-δp(n)p-1. So we assume pn.

Let nKnK-1n0 be the p-adic representation of n. Then

n-δp(n)p-1 =k=1Knk(j=0k-1pj)

Title the prime power dividing a factorialMathworldPlanetmath
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