2
$\begingroup$

If $p^f$ is the largest power of a prime $p$ such that $p^f|n$, then

$p\text{ does not divide }n\text{ choose }p^{f}\text{ (not sure on syntax for combinatorials).}$

The proof in Artin's Algebra is outlined by this claim, which I haven't been able to verify.

$n-k$ is divisible by the same maximal power of $p$ as $p^{f} - k$.

  • 0
    `\binom{n}{p^f}` gives you $\binom{n}{p^f}$.2012-10-12

1 Answers 1

1

Let $\xi := \binom{n-1}{p^f - 1}$. Then you have $\binom{n}{p^f} = \frac{n}{p^f}\prod_{j=1}^{p^f - 1} \frac{n - j}{p^f - j} = \frac{n}{p^f}\cdot \xi.$

For each $j$ write $j = p^{e_j} \cdot \lambda_j$ where $p$ doesn't divide $\lambda_j$.

Then $\prod_{j=1}^{p^f - 1} (n - j) = \prod_j (p^{f - e_j} - \lambda_j) = px + \prod_j (-\lambda_j)$ as well as $\prod_{j=1}^{p^f - 1} (p^f - j) = py + \prod_j (-\lambda_j)$ for some integers $x,y$. Letting $a := \prod_j (-\lambda_j)$ we have $\xi = \prod_{j=1}^{p^f - 1} \frac{n-j}{p^f - j} = \frac{xp + a}{yp + a},$ so $a(\xi - 1) = p(x-y)$. Since none of the $\lambda_j$ was divisible by $p$, $a$ isn't either.

So $p | \xi - 1$, and so $\xi \equiv 1 (\bmod p)$.

In particular, $p$ divides neither $\xi$ nor $\frac{n}{p^f}$ (by def. of $f$) and so it doesn't divide their product.

  • 0
    Thanks for this, will accept as soon as I finish working through your steps. :)2012-10-12