divisibility of prime-power binomial coefficients

For $p$ a prime, $n$ a nonzero integer, define $\operatorname{ord}_{p}(n)$ to be the largest integer $r$ such that $p^{r}\mid n$ .

An easy consequence of Kummer’s theorem is:

Theorem 1.

Let $p$ be a prime, $n\geq 1$ an integer. If $1\leq rp^{s}\leq p^{n}$ where $r, s$ are nonnegative integers with $p\nmid r$ , then $\operatorname{ord}_{p}\binom{p^{n}}{rp^{s}}=n-s$ .

Proof.

The result is clearly true for $r=1,s=n$ , so assume that $s<n$ . By Kummer’s theorem, $\operatorname{ord}_{p}\binom{p^{n}}{rp^{s}}$ is the number of carries when adding $rp^{s}$ to $p^{n}-rp^{s}$ in base $p$ . Consider the base $p$ representations of $rp^{s}$ and $p^{n}-rp^{s}$ . 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 $rp^{s}$ is $k$ , then the rightmost nonzero digit in $p^{n}-rp^{s}$ is in the same “decimal” place and has value $p-k$ . Each pair of corresponding digits (one from $rp^{s}$ and one from $p^{n}-rp^{s}$ ) 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+1^{\mathrm{st}}$ place and out of each successive place up to and including the $n^{\mathrm{th}}$ place, for a total of $n-s$ carries. ∎

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

\dbinom{27}{4}=17550=2\cdot 3^{3}\cdot 5^{2}\cdot 13

so that $\operatorname{ord}_{3}\binom{27}{4}=3$ . Now, $27_{10}=1000_{3}$ and $4_{10}=11_{3}$ , so that $27-4=23_{10}$ is $212_{3}$ . Adding $212_{3}+11_{3}$ indeed results in carries out of all three places since there are no trailing zeros.

\dbinom{27}{6}=296010=2\cdot 3^{2}\cdot 5\cdot 11\cdot 13\cdot 23

so that $\operatorname{ord}_{3}\binom{27}{6}=2$ . Now, $6_{10}=20_{3}$ so that $27-6=21_{10}$ is $210_{3}$ . When adding $20_{3}+210_{3}$ , 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