A community for students.
Here's the question you clicked on:
 0 viewing
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!(pk)!}\) is divisible by \(p\)?
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!(pk)!}\) is divisible by \(p\)?

This Question is Closed

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0Euclid's lemma states that if \(pab\), then \(pa\) and/or \(pb\).

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0Do you want me to show you what I have so far?

asnaseer
 4 years ago
Best ResponseYou've already chosen the best response.2surely p! (in the numerator) is ALWAYS divisible by p?

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0Proof:\[\frac{p!}{k!(pk)!}=\frac{1\cdot2\cdot...\cdot(p1)\cdot p}{1\cdot2\cdot...\cdot k\cdot[1\cdot2\cdot...\cdot(pk1)\cdot(pk)]}.\]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
 4 years ago
Best ResponseYou've already chosen the best response.2yes  that is what I was trying to say in the earlier statement.

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0But my mentor is asking me to use Euclid's lemma. :/

asnaseer
 4 years ago
Best ResponseYou've already chosen the best response.2ok  let me think about it...

asnaseer
 4 years ago
Best ResponseYou've already chosen the best response.2ok, maybe something like this: if p is prime, then none of the integers in k! or (pk)! can be factors of p therefore all the integers in k! and (pk)! 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 dab. Then if d is relatively prime to a, then d divides b.

asnaseer
 4 years ago
Best ResponseYou've already chosen the best response.2ah  hang on, maybe this will work:\[\frac{p!}{k!(pk)!}=p\times\frac{(p1)!}{k!(pk)!}\]now we know that k!(pk)! is relatively prime to p, therefore k!(pk)! divides (p1)!

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0Oh! I didn't think of separating the fraction like that.

asnaseer
 4 years ago
Best ResponseYou've already chosen the best response.2yes I think that works with one change in the statement: now we know that all the integers in k!(pk)! are relatively prime to p, therefore some of the integers in k!(pk)! must divide (p1)!

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0I can't thank you enough for your help, but I'm a little confused: doesn't Euclid's lemma first assume that dab? That's what we're trying to show. :/

asnaseer
 4 years ago
Best ResponseYou've already chosen the best response.2hmmm..  good point  needs more thought...

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0I don't know. I mean, maybe my professor skimmed through this problem because wouldn't simply showing that\[\frac{p!}{k!(pk)!}=p\cdot\frac{(p1)!}{k!(pk)!}\]immediately imply that the whole thing is divisible by \(p\)?

asnaseer
 4 years ago
Best ResponseYou've already chosen the best response.2yes  you are right. maybe there is something he forgot to state about the problem.
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.