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 fp(x) denote the highest power of prime p that divides x, we wish to know the value of fp(n!). This enables us to determine the powers of primes dividing multinomial coefficients, and so on. There is a nice formula for fp(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, n1, n2, ..., 1. Of these numbers, those that are divisible by at least one power of p are all the multiples of p less than n n0, of which there are exactly (n n0)/p. Of these numbers, some are divisible by two powers of p, namely, all the multiples of p2 less than n n0 n1p, of which there are exactly (n n0 n1p)/p2. 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 pk+1, we arrive at



Noting that the coefficients of n and n0 in the numerator are the partial geometric sum [pk + pk1 + ... + p + 1] and the coefficients of n1, n2,... are truncated copies of this, we see that the expression can be simplified if we multiply through by p1. 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 (p1)fp(n!) = n sp(n) where sp(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 (p1) 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 pt, we see that f(k) increases by t and s(k) changes by 1 (p1)f(k).


Return to MathPages Main Menu