# Combinatorial proof: $p^{r-n}$ divides $\binom{p^{r-2}}{n}$

Let $p$ be an odd prime. Then if $1<n<r$, $$p^{r-n}\,\left|\,\binom{p^{r-2}}{n}\right.$$ Does anyone have a clever combinatorial proof of this fact? There's an easy argument just by counting multiples of $p$ (with multiplicity) in the numerator and denominator, but it feels a bit clumsy, and this sort of thing ought to have a more elegant argument.

This problem arises naturally when looking at the structure of groups of the form $(\mathbb{Z}/n)^*$, which is why I've posted the above problem with what appears to be a stronger-than-necessary hypothesis and what is certainly a weaker-than-necessary conclusion.

-
I changed the $p^r$ in the title to $p^{r-n}$ as in the body. Please verify that this is correct. –  Alex Becker Jan 29 '13 at 5:42
@AlexBecker It is, thank you. –  Brett Frankel Jan 29 '13 at 5:45
There goes 20 minutes trying to induct on $n$ and then $r$... –  tacos_tacos_tacos Jan 29 '13 at 6:34
It appears I've been downvoted. I'd be interested in knowing why. –  Brett Frankel Jan 30 '13 at 1:02

EDIT: Made the proof a lot cleaner, and removed the induction.

First, let $n = mp^{k}$ with $p^k$ the highest power of $p$ dividing $n$. I claim that $r-2-k \ge r-n$. Indeed, this is the requirement that $n\ge 2+k$. This can be proven using induction on $k$, starting from the base case of $k=1$ when $m=1$, and from $k=0$ when $m>1$.

Consider the $n$ element subsets $S$ of the group $G = (\mathbb{Z}_p)^{r-2}$. The number of such subsets is certainly $p^{r-2} \choose n$. Let $G$ act on its $n$ element subsets by translation (left addition). What are the sizes of the orbits of $G$?

Well, there can be at most $k$ linearly independent elements that stabilize a given set $S$, because $S$ is a disjoint union of orbits of its own stabilizer. So by the orbit stabilizer theorem, a given orbit has order a multiple of $|G|/p^k = p^{r-2-k}$. Since $r-n \le r-2-k$, we have that $p^{r-n}$ divides the order of each orbit, and the proof is complete.

-

There is a nice result of Kummer that says that if $p^e$ is the highest power of the prime $p$ which divides $\dbinom{a}{b}$, then $e$ equals the number of carries in the sum $b + (a-b) = a$, where $b, a-b, a$ are written in base $p$.

So in your case it seems to me that you have only to show that $n < p^{n-1}$ (which guarantees that you will need at least $r - n$ carries when doing the sum $n + (p^{r-2} - n)$ in base $p$), and this holds indeed for $n > 1$ and $p$ odd.

-
Another way of saying this is $$e=\frac{\sigma_p(b)+\sigma_p(a-b)-\sigma_p(a)}{p-1}$$ where $\sigma_p(n)$ is the sum of the digits in the base-$p$ representation of $n$. –  robjohn Feb 4 '13 at 1:06