Theorem: N =  [n/p] + [n/p²] + [n/p³] + ...

Theorem:  Let N be the highest power of p that divides n!.  Then N is the sum

N =  [n/p] + [n/p²] + [n/p³] + ...

On our page on division lemmas, we said that, where p is a prime and a is a natural number not divisible by p, the only positive multiples of a that are divisible by p are:

a·p, a·2p, a·3p, ...   (sequence 1)

Now, let S_n be the set of the first n natural numbers.  It follows from the lemma, above, that

the number of elements of S_n that are divisible by p is [n/p].

By similar arguments, the following sequence of statements are all true:

the number of elements of S_n that are divisible by p² is [n/p²],
the number of elements of S_n that are divisible by p³ is [n/p³],
the number of elements of S_n that are divisible by p⁴ is [n/p⁴],
etc.

Note that if e_k is the exponent of the highest power of p that is divides k, then e_k is also the number of elements of {p, p², p³, ...} that divide k.  Therefore, the sum of all e_k for all the k from 1 to n is the sum of the sums of all the elements of S_n that are divisible by all the powers of p.  The sum of all e_k for all the k from 1 to n is the exponent of the highest power of p that divides n!.  That is,

N =  [n/p] + [n/p²] + [n/p³] + ...

which proves the theorem.

Internet references

Related pages in this website

Counting Primes method of proving the following are integers: C(n,k) = n!/(k!(n-k)!), (2a)!(2b)!/((a+b)!a!b!)

Combination identities proves the standard combination identities, including C(n,k) = C(n-1,k-1) + C(n-1,k) and many others.

Floor Function Identities, which are used in proofs that combinatorial identities are integers

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]