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_{0}, of which there are exactly (n – n_{0})/p. Of these numbers, some are divisible by two powers of p, namely, all the multiples of p^{2} less than n – n_{0} – n_{1}p, of which there are exactly (n – n_{0} – n_{1}p)/p^{2}. 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_{0} in the numerator are the partial geometric sum [p^{k} + p^{k–1} + ... + p + 1] and the coefficients of n_{1}, n_{2},... 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 righthand 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 basep 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 basep 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 nonmultiple 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). 
