Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.