How can I use Euclid's lemma to prove that if $p$ is a prime number with $1\leq k

Question

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

anonymous · Answer

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

anonymous · Answer

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

asnaseer · Answer

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

anonymous · Answer

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$

asnaseer · Answer

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

anonymous · Answer

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

asnaseer · Answer

ok - let me think about it...

asnaseer · Answer

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.

asnaseer · Answer

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)!

anonymous · Answer

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

asnaseer · Answer

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)!

anonymous · Answer

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. :/

asnaseer · Answer

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

anonymous · Answer

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

asnaseer · Answer

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