Binomial Coefficient - Divisibility Properties

Divisibility Properties

In 1852, Kummer proved that if m and n are nonnegative integers and p is a prime number, then the largest power of p dividing equals pc, where c is the number of carries when m and n are added in base p. Equivalently, the exponent of a prime p in equals the number of nonnegative integers j such that the fractional part of k/pj is greater than the fractional part of n/pj. It can be deduced from this that is divisible by n/gcd(n,k). In particular therefore it follows that p divides for all positive integers r and s such that s < pr. However this is not true of higher powers of p: for example 9 does not divide .

A somewhat surprising result by David Singmaster (1974) is that any integer divides almost all binomial coefficients. More precisely, fix an integer d and let f(N) denote the number of binomial coefficients with n < N such that d divides . Then

Since the number of binomial coefficients with n < N is N(N + 1) / 2, this implies that the density of binomial coefficients divisible by d goes to 1.

Another fact: An integer n ≥ 2 is prime if and only if all the intermediate binomial coefficients

are divisible by n.

Proof: When p is prime, p divides

for all 0 < k < p

because it is a natural number and the numerator has a prime factor p but the denominator does not have a prime factor p.

When n is composite, let p be the smallest prime factor of n and let k = n/p. Then 0 < p < n and

otherwise the numerator k(n−1)(n−2)×...×(n−p+1) has to be divisible by n = k×p, this can only be the case when (n−1)(n−2)×...×(n−p+1) is divisible by p. But n is divisible by p, so p does not divide n−1, n−2, ..., n−p+1 and because p is prime, we know that p does not divide (n−1)(n−2)×...×(n−p+1) and so the numerator cannot be divisible by n.