# $(p,\frac{n}{p^\alpha})=1$ then $p\nmid\binom{n}{p^\alpha}$

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.

-

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

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

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

-

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

-