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

Question

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.

Answer 1

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$.

Let $G = (\mathbb{Z}_p)^{r-2}$, and let $S$ denote the set of $n$ element subsets of $G$. Then $|S| = {p^{r-2} \choose n}$. Let $G$ act on $S$ by translation. That is, for $s \in S$, $s$ is some subset $\{g_1,\dots,g_n\} \subseteq G$. We define the action of $g \in G$ by $gs = \{g+ g_1,\dots,g+g_n\}$.

For any given $s \in S$, the size of the stabilizer $G_s$ must divide $n$. Indeed, since $G_s s = s$, we can think of $G_s$ as actually acting on the set $s = \{g_1,\dots,g_n\}$ by translation. Since $G_s$ acts freely, we see that $|G_s|$ divides $|s| = n$. Moreover, since $|G_s|$ must divide $|G| = p^{r-2}$, $|G_s|$ must be a power of $p$. So $|G_s|$ is a power of $p$ dividing $n=mp^k$, so in fact it divides $p^k$.

Now we can look at the size of the orbits of $S$ using the orbit-stabilizer theorem. Since the size of every stabilizer $G_s$ divides $p^k$, the size of every orbit must be 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 every orbit. $|S|$ is a union of all the orbits, so $p^{r-n}$ must also divide $|S| = {p^{r-2} \choose n}$, and the proof is complete.

Answer 2

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.