5
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$$ $\endgroup$ – stefan-niculae Apr 13 '14 at 16:34
  • $\begingroup$ My first identity implies $$p^n |k\times \binom{p^n}{k}$$. I consider two different cases after that. $\endgroup$ – Gabriel Romon Apr 13 '14 at 16:40
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – stefan-niculae Apr 13 '14 at 16:31
  • $\begingroup$ @StefanNiculae A stray factorial got in there where it shouldn't be ... $\endgroup$ – Mark Bennet Apr 13 '14 at 16:33
  • $\begingroup$ Oh, I am sorry, there has been a mistake, now I understand. $\endgroup$ – stefan-niculae Apr 13 '14 at 16:37
  • $\begingroup$ 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. $\endgroup$ – Mark Bennet Apr 13 '14 at 16:43
  • $\begingroup$ 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 } $ $\endgroup$ – stefan-niculae Apr 13 '14 at 17:09
0
$\begingroup$

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.

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

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<k<p^n,$

  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.

$\endgroup$

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.