
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^{2}] + [n/p^{3}] + ...
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=1p(k)
The numbers from 1 to n that are divisible by p are A_{1} = {p, 2p,
3p, ..., [n/p] p }
The numbers from 1 to n that are divisible by p^{2} are A_{2} =
{p^{2}, 2p^{2}, 3p^{2}, ..., [n/p^{2}] p^{2}
}
The numbers from 1 to n that are divisible by p^{3} are A_{3} =
{p^{3}, 2p^{3}, 3p^{3}, ..., [n/p^{3}] p^{3}
}
etc.
More formally, set A_{i} contains the numbers from 1 to n that are divisible by p^{i}. 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^{i}], so
N = ∞
Σ
i=1[n/p^{i}],
proving the theorem.
The webmaster and author of this Math Help site is Graeme McRae.