A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 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!(p-k)!}\) is divisible by \(p\)?

  • This Question is Closed
  1. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  2. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  3. asnaseer
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  4. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  6. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  7. asnaseer
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    ok - let me think about it...

  8. asnaseer
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  11. asnaseer
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  14. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  16. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.