# 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

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.

-
Why can't $S$ have more than k independent stabilizers? I don't get "$S$ is a disjoint union of orbits of its own stabilizer". (If $v \in G$ stabilizes $S$, so $v+S=S$, its orbit $G+v$ is not contained in $S$, so what does this sentence mean?) – Leullame Jan 24 at 18:41
@Leullame Did a big rewrite, let me know if you still have questions. Hopefully I'm better at writing math these days. – Carl Jan 29 at 19:25
Thank you very much for your effort. I don't see why $G_s$ acts transitively on $s$; for given $g_i,g_j \in s$, the element sending $g_i$ to $g_j$ is $g_j-g_i$ which is not necessarily in $G_s$. Furthermore, being transitive seems to imply the reverse direction: $n \big| |G_s|$. However, thanks to your explanations I think the original wording shows $|G_s| \big| n$: for each $g_i \in s$, the stabilizer of $g_i$ is $0$, since we require $g+g_i=g_i$. Thus the orbit of $g_i$ is of size $|G_s|$, and $s$ is a disjoint union of orbits, each of size $G_s$. Hence $n=|s|$ is divisible by $|G_s|$. – Leullame Jan 30 at 20:58
@Leullame Thanks, you're right.. I changed the word "transitively" to "freely", and that is probably what I meant by that "union of the orbits of its stabilizer" line. – Carl Feb 1 at 4:32

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