6
$\begingroup$

Is there a simple way of showing that a prime $p$ must divide the binomial coefficient $p^n\choose{k}$ for all $n\geq 1$ and $1\leq k\leq p^n-1$?

$\endgroup$
11
$\begingroup$

$$\binom{p^n}{k} = \frac{p^n (p^n -1) ... (p^n -k+1)}{k!}= \frac{p^n}{k} \cdot \frac{ (p^n -1) ... (p^n -k+1) }{(k-1)!} = \frac{p^n}{k} \cdot \underbrace{\binom{p^n -1}{k-1}}_{\in \mathbb{Z}} $$

$p \Big| p^n$ and because $k<p^n$ we get that $$p \Big| \binom{p^n}{k}$$ Q.E.D

$\endgroup$
8
  • $\begingroup$ I must be missing something simple: why does $p\mid p^n$, from the previous line? $\endgroup$
    – Clement C.
    Mar 29 '16 at 14:08
  • $\begingroup$ This is immediate. $\endgroup$
    – Yonatan
    Mar 29 '16 at 14:17
  • 1
    $\begingroup$ @ClementC. The highest power of $p$ that can divide $k$ is $p^{n-1}$. All other factors of $k$ divide $\binom{p^n -1}{k-1}$. This leaves at least one factor of $p$ remaining. $\endgroup$ Mar 29 '16 at 17:44
  • 1
    $\begingroup$ @PaulSinclair OK. (This may be splitting hair, but the point of my comments is that adding that to the answer may have been a good thing.) $\endgroup$
    – Clement C.
    Mar 29 '16 at 17:45
  • 1
    $\begingroup$ @ClementC. - agreed. This is a little much to have been left unsaid. $\endgroup$ Mar 29 '16 at 17:46
8
$\begingroup$

In this answer is is shown that the number of factors of $p$ that divide $\binom{n}{k}$ is $$ \frac{\sigma_p(k)+\sigma_p(n-k)-\sigma_p(n)}{p-1}\tag{1} $$ where $\sigma_p(n)$ is the sum of the digits in the base-$p$ representation of $n$.

Since $\sigma_p\!\left(p^n\right)=1$ and $k,p^n-k\ne0$, we have that $\sigma_p(k),\sigma_p\!\left(p^n-k\right)\ge1$. Thus, $$ \frac{\sigma(k)+\sigma\!\left(p^n-k\right)-\sigma\!\left(p^n\right)}{p-1}\gt0\tag{2} $$ Therefore, the number of factors of $p$ that divide $\binom{p^n}{k}$ is greater than $0$.

$\endgroup$
2
  • $\begingroup$ Nice. To make it less depending on the link you could add a definition of $\sigma_p$. $\endgroup$
    – drhab
    Mar 29 '16 at 12:55
  • $\begingroup$ @drhab: good idea. Thanks! $\endgroup$
    – robjohn
    Mar 29 '16 at 12:59
5
$\begingroup$

Just a quick remark after the fact: If you accept that $$ (a +b )^{p} \equiv a^p +b^p\pmod p ,$$ for $a$ and $b$ indeterminants, then $$(a+b)^{p^n} = \left(\ (a + b )^p\ \right)^{p^{n-1}}\equiv \left(\ a^p + b^p\ \right)^{p^{n-1}}\equiv a^{p^n}+ b^{p^n}\pmod p,$$ which also gives the result.

$\endgroup$
2
  • $\begingroup$ Indeed, this is even easier! $\endgroup$
    – geometricK
    Mar 30 '16 at 7:08
  • $\begingroup$ I don't know about that! I liked Yonatan's answer too. $\endgroup$
    – peter a g
    Mar 30 '16 at 11:32
4
$\begingroup$

$$\begin{align*}\binom{p^n}{k} = \frac{(p^n)!}{k! (n-k)!} &= \frac{(p^n)(p^n-1)(p^n-2)(p^n-3)\cdots (p^n-(k-1))}{1\cdot 2\cdot 3 \cdots (k-1)k} \\ &= \frac{p^n}{k}\cdot \frac{p^n-1}{1} \cdot \frac{p^n-2}{2}\cdots \frac{p^n-(k-1)}{k-1} \\ &= \frac{p^n}{k} \cdot \prod_{i=1}^{k-1} \frac{p^n-i}{i}.\end{align*}$$ (Note that these smaller fractions are not necessarily integers.)

We are trying to show that after all cancellations of prime factors, there remains at least one factor of $p$ in the numerator of this large fraction.

Consider the fractions of the form $\frac{p^n-i}{i}$. Now $p^n-i$ is divisible by $p^j$ if and only if $i$ is divisible by $p^j$, for all $1\leq j\leq n$. So in each fraction $\frac{p^n-i}{i}$, all the $p$'s in the numerator and denominator cancel perfectly. So in the entire fraction, the only remaining $p$'s in the numerator are those in $p^n$, and the only remaining $p$'s in the denominator (if any) are factors of $k$. But $k<p^n$, so $k$ can have at most $n-1$ factors of $p$, leaving at least one left over in the numerator.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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