Powers of Primes Dividing Factorials

It's often useful to know the highest power of a given prime p that divides n! for a given positive integer n. Letting f_p(x) denote the highest power of prime p that divides x, we wish to know the value of f_p(n!). This enables us to determine the powers of primes dividing multinomial coefficients, and so on. There is a nice formula for f_p(n!), apparently first discussed by Legendre, involving the sum of the digits of n when n is expressed in the base p. Writing the number n in the base p we have

The number of powers of p dividing n! is just the sum of the powers of p dividing each of the numbers n, n–1, n–2, ..., 1. Of these numbers, those that are divisible by at least one power of p are all the multiples of p less than n – n₀, of which there are exactly (n – n₀)/p. Of these numbers, some are divisible by two powers of p, namely, all the multiples of p² less than n – n₀ – n₁p, of which there are exactly (n – n₀ – n₁p)/p². Continuing on in this way we find that the total number of powers of p dividing n! is the sum

Placing all these fractions on a common denominator of p^k+1, we arrive at

Noting that the coefficients of n and n₀ in the numerator are the partial geometric sum [p^k + p^k–1 + ... + p + 1] and the coefficients of n₁, n₂,... are truncated copies of this, we see that the expression can be simplified if we multiply through by p–1. Letting j denote k+1, this leads to the expression

The expression inside the parentheses in the numerator of the right-hand fraction is simply n, so the fraction vanishes and we are left with (p–1)f_p(n!) = n – s_p(n) where s_p(n) denotes the sum of the base-p digits of n. Therefore, we have proven Legendre's result that

Obviously we can then express the powers of p dividing the binomial coefficient C(m+n,n) = (m+n)!/((m!)(n!)) as (omitting the subscripts)

This is interesting because it shows that the number of powers of p dividing C(m+n,n) is a measure of the extent to which the operations of addition and s() are not distributive. For each of the infinitely many primes p that do not divide C(m+n,n) we have

but for a prime p that divides C(m+n,n) this equality doesn't hold, and the extent to which it doesn't hold equals (p–1) times the number of powers of p that divide C(m+n,n). Of course, the above identity also allows us to express the binomial coefficients as the product of powers of primes

where the product is evaluated over all primes. We can also easily verify that, for any fixed prime p, consecutive values of s() are related to consecutive values of f() as follows

This is clear simply by examining the sequence of base-p expressions, such as (in the base 5)

For the steps in between multiples of p the value of f(k) is zero and the sum of the digits increases by 1. When going from a non-multiple of p to a multiple of p^t, we see that f(k) increases by t and s(k) changes by 1 – (p–1)f(k).

Return to MathPages Main Menu