# divisibility of prime-power binomial coefficients

For $p$ a prime, $n$ a nonzero integer, define ${\mathrm{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\mathrm{\ge}\mathrm{1}$ an integer. If $\mathrm{1}\mathrm{\le}r\mathit{}{p}^{s}\mathrm{\le}{p}^{n}$ where $r\mathrm{,}s$ are nonnegative integers with $p\mathrm{\nmid}r$, then ${\mathrm{ord}}_{p}\mathit{}\mathrm{\left(}\genfrac{}{}{0pt}{}{{p}^{n}}{r\mathit{}{p}^{s}}\mathrm{\right)}\mathrm{=}n\mathrm{-}s$.

###### Proof.

The result is clearly true for $r=1,s=n$, so assume that $$. By Kummer’s theorem, ${\mathrm{ord}}_{p}\left(\genfrac{}{}{0pt}{}{{p}^{n}}{r{p}^{s}}\right)$ is the number of carries when adding $r{p}^{s}$ to ${p}^{n}-r{p}^{s}$ in base $p$. Consider the base $p$ representations of $r{p}^{s}$ and ${p}^{n}-r{p}^{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 $r{p}^{s}$ is $k$, then the rightmost nonzero digit in ${p}^{n}-r{p}^{s}$ is in the same “decimal” place and has value $p-k$. Each pair of corresponding digits (one from $r{p}^{s}$ and one from ${p}^{n}-r{p}^{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

$$\left(\genfrac{}{}{0pt}{}{27}{4}\right)=17550=2\cdot {3}^{3}\cdot {5}^{2}\cdot 13$$ |

so that ${\mathrm{ord}}_{3}\left(\genfrac{}{}{0pt}{}{27}{4}\right)=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.

$$\left(\genfrac{}{}{0pt}{}{27}{6}\right)=296010=2\cdot {3}^{2}\cdot 5\cdot 11\cdot 13\cdot 23$$ |

so that ${\mathrm{ord}}_{3}\left(\genfrac{}{}{0pt}{}{27}{6}\right)=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 |