Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
    
Indeed, this is even easier! – ougoah Mar 30 at 7:08
    
I don't know about that! I liked Yonatan's answer too. – peter a g Mar 30 at 11:32

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

share|cite|improve this answer
    
I must be missing something simple: why does $p\mid p^n$, from the previous line? – Clement C. Mar 29 at 14:08
    
This is immediate. – Yonatan Mar 29 at 14:17
1  
@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. – Paul Sinclair Mar 29 at 17:44
1  
@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.) – Clement C. Mar 29 at 17:45
1  
@ClementC. - agreed. This is a little much to have been left unsaid. – Paul Sinclair Mar 29 at 17:46

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

share|cite|improve this answer
    
Nice. To make it less depending on the link you could add a definition of $\sigma_p$. – drhab Mar 29 at 12:55
    
@drhab: good idea. Thanks! – robjohn Mar 29 at 12:59

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

share|cite|improve this answer
    
+1 nice demonstration. – Paul Sinclair Mar 29 at 17:49

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.