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 $n=p^\alpha m$ wherein $(p,m)=1$. Then we have $$p\nmid\binom{n}{p^\alpha}$$ What I have done is just playing with $\binom{n}{p^\alpha}$ like:$$\binom{n}{p^\alpha}=\frac{n!}{(n-p^\alpha)!p^\alpha!}=m\binom{p^\alpha m-1}{p^\alpha-1}$$

Honestly, the rest is unclear to me. Thank you for your help.

EDIT: $p$ is prime.

share|improve this question

4 Answers 4

up vote 1 down vote accepted

I assume that $p$ is prime.

Kummer's Theorem says that the number of factors of $p$ in $\binom{n}{k}$ is the sum of the base-$p$ digits of $n$ minus the sum of the base-$p$ digits of $k$ and $n-k$, all divided by $p-1$.

In the case above, the base-$p$ representation of $n$ looks like $$ d_md_{m-1}d_{m-2}\dots d_{\alpha}\underbrace{000\dots000}_{\alpha\text{ zeros}} $$ where $d_\alpha\not=0$. Furthermore, $p^\alpha$ looks like $$ 1\underbrace{000\dots000}_{\alpha\text{ zeros}} $$ and $n-p^\alpha$ looks like $$ d_md_{m-1}d_{m-2}\dots (d_{\alpha}-1)\underbrace{000\dots000}_{\alpha\text{ zeros}} $$ The sum of the base-$p$ digits in $n-p^\alpha$ and $p^\alpha$ is $$ \sum_{j=\alpha}^md_j $$ which is the same as the sum of the base-$p$ digits in $n$. Thus, there are no factors of $p$ in $\binom{n}{p^\alpha}$.

share|improve this answer
1  
Just in case anyone is unfamiliar with the result, I would mention that this is Kummer's Theorem. –  EuYu Aug 21 '12 at 20:52
    
@EuYu: Thanks; I was looking for the name, and a reference. –  robjohn Aug 21 '12 at 21:08

I assume $p$ is a prime. This follows from Lucas theorem. If you wrote $n$ in base $p$, both $p^\alpha$ and $n$ end in $\alpha$ zeroes. At no point does $p^\alpha$ have a digit greater than that of $n$ therefore $\binom{n}{p^\alpha} \neq 0~(mod~p)$.

share|improve this answer
    
Thank you for your answer. –  Babak S. Aug 23 '12 at 8:04

You can show this with a polynomial identity. Consider the polynomial $P(X)=(X+1)^n\in\Bbb Z/p\Bbb Z[X]$. By the binomial theorem, $$P(X)=\sum_{k=0}^n\binom{n}{k}X^k.$$ We can also use the Frobenius morphism of $\Bbb Z/p\Bbb Z[X],~Q(X)\mapsto Q(X)^p$ (which is a ring homomorphism) and write $$P(X)=(X+1)^n=(X+1)^{p^{\alpha}m}=\big((X+1)^{p^{\alpha}}\big)^m=\big(X^{p^{\alpha}}+1\big)^m=\sum_{k=0}^m\binom{m}{k}X^{p^{\alpha}k}$$ Comparing the coefficients in both expressions, we have, for $k=0,\dots,m$ and modulo $p$: $$\binom{p^{\alpha}m}{p^{\alpha}k}=\binom{m}{k}$$ and therefore (for $k=1$) $$\binom{p^{\alpha}m}{p^{\alpha}}=\binom{m}{1}=m\neq 0$$ since $m$ and $p$ are coprime, i.e. $p$ does not divide $\binom{p^{\alpha}m}{p^{\alpha}}$. This als shows that if $k$ is not a multiple of $p^{\alpha}$, then $\binom{n}{k}$ is a multiple of $p$.

share|improve this answer

$\displaystyle {n \choose p^\alpha} = \frac{n}{p^\alpha} \frac{n-1}{p^\alpha - 1} \dots \frac{n-p^\alpha+1}{1}$

So just observe that $\mathrm{ord}_p (n-k) = \mathrm{ord}_p (p^\alpha - k)$ for all $0 \le k < p^\alpha$, where $\mathrm{ord}_p$ is the power of $p$ in the prime decomposition.

P.S. By the way, this also works if $p$ is not prime: just replace $\mathrm{ord}_p$ by $\mathrm{ord}_q$, where $q$ is a prime factor of $p$.

share|improve this answer

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.