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/p²] + [n/p³] + ...

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

The numbers from 1 to n that are divisible by p are A₁ = {p, 2p, 3p, ..., [n/p] p }
The numbers from 1 to n that are divisible by p² are A₂ = {p², 2p², 3p², ..., [n/p²] p² }
The numbers from 1 to n that are divisible by p³ are A₃ = {p³, 2p³, 3p³, ..., [n/p³] p³ }
etc.

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

 proving the theorem.

Internet references

Related pages in this website

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