Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Theorems > Factorial Divisors

Highest power of p that divides n!

Let n be a natural number, and let p be a prime.  Then the exponent of the highest power of p that divides n! is equal to

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

Proof:  The largest exponent of p that divides n! is equal to the sum of the largest exponents of p that divide 1, 2, 3, ..., n.  If we let p(k) represent the largest exponent of p that divides k, then the number we're looking for is

N =  n
Σ
k=1
p(k)

The numbers from 1 to n that are divisible by p are A1 = {p, 2p, 3p, ..., [n/p] p }
The numbers from 1 to n that are divisible by p2 are A2 = {p2, 2p2, 3p2, ..., [n/p2] p2 }
The numbers from 1 to n that are divisible by p3 are A3 = {p3, 2p3, 3p3, ..., [n/p3] p3 }
etc.

More formally, set Ai contains the numbers from 1 to n that are divisible by pi.  Each of the Ai is a subset of all the Aj with j<i.  Each number, k, 1≤k≤n, is an element of all of the sets Aj, where i≤p(k).  In other words, k appears as an element in p(k) of the Ai sets.  So by counting the number of elements in all of the Ai sets, we will find the sum from 1 to n of p(k), as required.  The number of elements of Ai is [n/pi], so

N =  ∞
Σ
i=1
[n/pi],

 proving the theorem.

Internet references

Related pages in this website

 

 

The webmaster and author of this Math Help site is Graeme McRae.