Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Theorems > Prime Factorization of n!

Theorem: N =  [n/p] + [n/p2] + [n/p3] + ...

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

N =  [n/p] + [n/p2] + [n/p3] + ...

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 Sn be the set of the first n natural numbers.  It follows from the lemma, above, that

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

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

the number of elements of Sn that are divisible by p2 is [n/p2],
the number of elements of Sn that are divisible by p3 is [n/p3],
the number of elements of Sn that are divisible by p4 is [n/p4],
etc.

Note that if ek is the exponent of the highest power of p that is divides k, then ek is also the number of elements of {p, p2, p3, ...} that divide k.  Therefore, the sum of all ek for all the k from 1 to n is the sum of the sums of all the elements of Sn that are divisible by all the powers of p.  The sum of all ek 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/p2] + [n/p3] + ...

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 this Math Help site is Graeme McRae.