# Proof that $p$ | ${ p^n \choose k }$ for any prime $p$ and $k < p^n$

I know how to prove the fact that $p$ | ${ p \choose k }$ (when writing it as a fraction, $p$ cannot be divided by any of the $1\times2\times...\times k$ or $1\times2\times...\times(p-k)$ because $p$ is prime).

When I try to apply the same rationale for $p$ | ${ p^n \choose k }$ I get stumped because $p^n$ is in fact divisible by one of the $k! = 1\times2\times...\times k$, where $0 < k < p^n$.

If we take the example of $2^3$ and $k = 7$, we can easily see that $k! = 1 \times 2 \times ... \times 6 \times 7$, and $2$ clearly divides $2^3$.

How else can I approach this?

The following identity holds:

$$\binom{p^n}{k}=\frac{p^n}{k} \binom{p^n-1}{k-1}.$$

Hence

$$k\binom{p^n}{k}=p^n\binom{p^n-1}{k-1}$$

which implies that $$p^n\mid k\binom{p^n}{k}.$$

• If $$p$$ and $$k$$ are coprime, then $$p^n \mid \binom{p^n}{k}$$, with $$p \mid p^n$$. This completes the proof.

• If they're not, then there exists a maximal $$\alpha and $$q \in \mathbb N$$ such that $$k=p^\alpha q$$ (note that $$q$$ and $$p$$ are coprime).

We have that $$q \binom{p^n}{k}=p^{n-\alpha} \binom{p^n-1}{k-1}$$ and $$n-\alpha \geq 1$$

Thus $$p\mid p^{n-\alpha}$$ and $$p^{n-\alpha}\mid \binom{p^n}{k}.$$

Finally $$p\mid \binom{p^n}{k}.$$

• I do not understand how $$k\times \binom{p^n}{k}=p^n\binom{p^n-1}{k-1}$$ helps me, since I want to prove that $$p | \binom{p^n}{k}$$, not $$k \times p | \binom{p^n}{k}$$ – stefan-niculae Apr 13 '14 at 16:34
• My first identity implies $$p^n |k\times \binom{p^n}{k}$$. I consider two different cases after that. – Gabriel Romon Apr 13 '14 at 16:40

This answer was started before the question was changed.

Note that the highest power of $p$ which divides $n!$ is $$\sum_{r=1}^\infty\left\lfloor\frac {n}{p^r}\right\rfloor$$ which is a finite sum because the terms eventually become zero.

The highest power of $p$ which divides $(p^n)!$ is $p^{n-1}+p^{n-2}+\dots 1=\cfrac {p^n-1}{p-1}$

The highest power of $p$ which divides $(kp^{n-1})!$, where $1\le k \lt p$, is $kp^{n-2}+kp^{n-3}+\dots +k=k\cfrac{p^{n-1}-1}{p-1}$

Now examine $$\binom {p^n}{kp^{n-1}}$$ Subtracting the two contributions made by the numerator from that made by the denominator, the total power of $p$ dividing this is $$\cfrac {p^n-1}{p-1}-k\cfrac {p^{n-1}-1}{p-1}-(p-k)\cfrac {p^{n-1}-1}{p-1}=\frac {p^n-1-kp^{n-1}-(p-k)p^{n-1}+k+(p-k)}{p-1}=1$$

This shows that the highest possible power of $p$ is always $1$.

This technique can be used to show that a power of $p$ will always divide the coefficient (except the ones which are $1$) and to analyse what power of $p$ that will be.

• I don't understand the part "The highest power of $p$ which divides $(p^n)!$ is $p^{n-1}+p^{n-2}+\dots 1=\cfrac {p^n-1}{p-1}$". If I apply the formula you have provided, I get $\cfrac{(p^n)!}{p} + \cfrac{(p^n)!}{p^2} + \dots + 1$ which is ${ (p^{n-1})!p^{n-1} + (p^{n-1})!p^{n-2} + ... +1}$ – stefan-niculae Apr 13 '14 at 16:31
• @StefanNiculae A stray factorial got in there where it shouldn't be ... – Mark Bennet Apr 13 '14 at 16:33
• Oh, I am sorry, there has been a mistake, now I understand. – stefan-niculae Apr 13 '14 at 16:37
• Let's use an example of $n=12, p=2$ there are $6$ even numbers less than or equal to $12$ - that is $12/2$. There are $3$ multiples of $4$, that is $12/4$ (they contribute two powers of $2$ - we counted them as one when we counted the even numbers, and so need to add one more). There is one multiple of $8$ which contributes an extra power of $2$. Now $12/8=1.5$ and we use the floor function to round it down to an integer. $6+3+1=10$. The floor function doesn't change an integer. – Mark Bennet Apr 13 '14 at 16:43
• Thank you for your explanations, I have understood the formula for the maximum power of p which divides n!, but I don't see how we get from $\binom {p^n}{kp^{n-1}}$ to $\cfrac {p^n-1}{p-1}-k\cfrac {p^{n-1}-1}{p-1}-(p-k)\cfrac {p^{n-1}-1}{p-1}$ or how that helps us prove that $p$ | ${ p^n \choose k }$ – stefan-niculae Apr 13 '14 at 17:09

Edit: The question was changed after the answer below was posted.

In general, it is not true that $p^n$ divides $\binom{p^n}{k}$. Let $p=2$, $n=2$, $k=2$. There are infinitely many examples.

• You are correct, there is a mistake in what I have written. I want p divides ${p^n \choose k}$ – stefan-niculae Apr 13 '14 at 15:34
• One standard way is to use the formula for the highest power of $p$ that divides $n!$. – André Nicolas Apr 13 '14 at 15:43

The highest prime power $$p$$ dividing $$n!$$ is expressed as $$\sum_{x=1}^\infty \lfloor \frac{n}{p^x} \rfloor.$$ Since $$\binom{p^n}{k}=\frac{(p^n)!}{k!(p^n-k)!},$$ we compare the highest prime power $$p$$ which divide numerator and denominator. $$v_p((p^n)!)=\sum_{x=1}^n \lfloor \frac{p^n}{p^x} \rfloor,$$ $$v_p(k!(p^n-k)!)=v_p(k!)+v_p((p^n-k)!)=\sum_{x=0}^n \left( \lfloor \frac{k}{p^x} \rfloor + \lfloor \frac{p^n-k}{p^x} \rfloor \right).$$ (We've replaced $$\infty$$ bound with $$n$$ since if $$x>n,$$ the terms evaluate to $$0$$).

Notice that $$\lfloor a+b \rfloor \ge \lfloor a \rfloor + \lfloor b \rfloor,$$ and the that if $$a+b$$ is an integer while $$a$$ and $$b$$ are not, then $$\lfloor a+b \rfloor = \lfloor a \rfloor + \lfloor b \rfloor - 1.$$ We can conclude with the first fact that $$\sum_{x=1}^n \lfloor \frac{p^n}{p^x} \rfloor \ge \sum_{x=0}^n \left( \lfloor \frac{k}{p^x} \rfloor + \lfloor \frac{p^n-k}{p^x} \rfloor \right).$$

Because

1. $$0

2. $$\frac{p^n}{p^x} \in \mathbb{Z}$$ for integers $$1 \le x \le n,$$

3. $$\frac{k}{p^x}+\frac{p^n-k}{p^x} \in \mathbb{Z}$$ for same bounds,

4. When $$x=n,$$ neither $$\frac{k}{p^x}$$ nor $$\frac{p^n-k}{p^x}$$ are integral $$\implies \lfloor \frac{p^n}{p^n} \rfloor = 1 > \lfloor \frac{k}{p^n} \rfloor + \lfloor \frac{p^n-k}{p^n} \rfloor = 0.$$

Finally, we can conclude $$\sum_{x=1}^n \lfloor \frac{p^n}{p^x} \rfloor > \sum_{x=0}^n \left( \lfloor \frac{k}{p^x} \rfloor + \lfloor \frac{p^n-k}{p^x} \rfloor \right).$$ This implies the divisibility.