divisibility of prime-power binomial coefficients
For a prime, a nonzero integer, define to be the largest integer such that .
An easy consequence of Kummer’s theorem is:
Let be a prime, an integer. If where are nonnegative integers with , then .
The result is clearly true for , so assume that . By Kummer’s theorem, is the number of carries when adding to in base . Consider the base representations of and . They each have digits (possibly with leading zeros) when represented in base , and they each have trailing zeros. If the rightmost nonzero digit in is , then the rightmost nonzero digit in is in the same “decimal” place and has value . Each pair of corresponding digits (one from and one from ) to the left of that point sum to (it may help to think about how you subtract a decimal number from a power of , and what the result looks like).
It is then clear that adding those two numbers together will result in no carries in the rightmost places, but there will be a carry out of the place and out of each successive place up to and including the place, for a total of carries. ∎
A couple of examples may help to make this proof more transparent. Take . Then
so that . Now, and , so that is . Adding indeed results in carries out of all three places since there are no trailing zeros.
so that . Now, so that is . When adding , there are two carries, out of the ’s place and out of the ’s place. There is no carry out of the ones place since both numbers have a there.
|Title||divisibility of prime-power binomial coefficients|
|Date of creation||2013-03-22 18:42:29|
|Last modified on||2013-03-22 18:42:29|
|Last modified by||rm50 (10146)|