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.
 A: 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.
A: 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.
