divisibility of prime-power binomial coefficients


For p a prime, n a nonzero integer, define ordp(n) to be the largest integer r such that prn.

An easy consequence of Kummer’s theorem is:

Theorem 1.

Let p be a prime, n1 an integer. If 1rpspn where r,s are nonnegative integers with pr, then ordp(pnrps)=n-s.

Proof.

The result is clearly true for r=1,s=n, so assume that s<n. By Kummer’s theorem, ordp(pnrps) is the number of carries when adding rps to pn-rps in base p. Consider the base p representations of rps and pn-rps. They each have n digits (possibly with leading zeros) when represented in base p, and they each have s trailing zeros. If the rightmost nonzero digit in rps is k, then the rightmost nonzero digit in pn-rps is in the same “decimal” place and has value p-k. Each pair of corresponding digits (one from rps and one from pn-rps) to the left of that point sum to p-1 (it may help to think about how you subtract a decimal number from a power of 10, and what the result looks like).

It is then clear that adding those two numbers together will result in no carries in the rightmost s places, but there will be a carry out of the s+1st place and out of each successive place up to and including the nth place, for a total of n-s carries. ∎

A couple of examples may help to make this proof more transparent. Take p=3. Then

(274)=17550=2335213

so that ord3(274)=3. Now, 2710=10003 and 410=113, so that 27-4=2310 is 2123. Adding 2123+113 indeed results in carries out of all three places since there are no trailing zeros.

(276)=296010=2325111323

so that ord3(276)=2. Now, 610=203 so that 27-6=2110 is 2103. When adding 203+2103 , there are two carries, out of the 3’s place and out of the 9’s place. There is no carry out of the ones place since both numbers have a 0 there.

Title divisibility of prime-power binomial coefficients
Canonical name DivisibilityOfPrimepowerBinomialCoefficients
Date of creation 2013-03-22 18:42:29
Last modified on 2013-03-22 18:42:29
Owner rm50 (10146)
Last modified by rm50 (10146)
Numerical id 4
Author rm50 (10146)
Entry type Theorem
Classification msc 05A10
Classification msc 11B65
Related topic OrderValuation