## anonymous 4 years ago How can I use Euclid's lemma to prove that if $$p$$ is a prime number with $$1\leq k<p$$, then $$\frac{p!}{k!(p-k)!}$$ is divisible by $$p$$?

1. anonymous

Euclid's lemma states that if $$p|ab$$, then $$p|a$$ and/or $$p|b$$.

2. anonymous

Do you want me to show you what I have so far?

3. asnaseer

surely p! (in the numerator) is ALWAYS divisible by p?

4. anonymous

Proof:$\frac{p!}{k!(p-k)!}=\frac{1\cdot2\cdot...\cdot(p-1)\cdot p}{1\cdot2\cdot...\cdot k\cdot[1\cdot2\cdot...\cdot(p-k-1)\cdot(p-k)]}.$However, since $$0<k<p$$ and $$p$$ is a prime number, notice that the $$p$$ in the numerator will never be cancelled out by any of the terms in the denominator. Therefore, p divides the above expression. $$\blacksquare$$

5. asnaseer

yes - that is what I was trying to say in the earlier statement.

6. anonymous

But my mentor is asking me to use Euclid's lemma. :/

7. asnaseer

ok - let me think about it...

8. asnaseer

ok, maybe something like this: if p is prime, then none of the integers in k! or (p-k)! can be factors of p therefore all the integers in k! and (p-k)! must be relatively prime to p hmmm - I can't see quite how to use Euclids Lemma here. The lemma itself states that: For two integers a and b, suppose d|ab. Then if d is relatively prime to a, then d divides b.

9. asnaseer

ah - hang on, maybe this will work:$\frac{p!}{k!(p-k)!}=p\times\frac{(p-1)!}{k!(p-k)!}$now we know that k!(p-k)! is relatively prime to p, therefore k!(p-k)! divides (p-1)!

10. anonymous

Oh! I didn't think of separating the fraction like that.

11. asnaseer

yes I think that works with one change in the statement: now we know that all the integers in k!(p-k)! are relatively prime to p, therefore some of the integers in k!(p-k)! must divide (p-1)!

12. anonymous

I can't thank you enough for your help, but I'm a little confused: doesn't Euclid's lemma first assume that d|ab? That's what we're trying to show. :/

13. asnaseer

hmmm.. - good point - needs more thought...

14. anonymous

I don't know. I mean, maybe my professor skimmed through this problem because wouldn't simply showing that$\frac{p!}{k!(p-k)!}=p\cdot\frac{(p-1)!}{k!(p-k)!}$immediately imply that the whole thing is divisible by $$p$$?

15. asnaseer

yes - you are right. maybe there is something he forgot to state about the problem.