Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Lemma Lucas theorem

  1. Oct 19, 2013 #1
    Hi. I dont understand the following proof.



    Lemma
    Let p be a prime number and 1<=k<=p-1, then:
    [itex]{p \choose k} \equiv 0 \pmod{p}[/itex]

    Proof

    [itex]{p \choose k} = \frac{p!}{k!(p-k)!}[/itex]. Since [itex]p | p![/itex] but [itex] p \not | k! \land p \not | (p-k)![/itex] the proof follows.

    I think here what you want to show is that p divides the binomial coefficient, but how does the proof do that?
     
    Last edited: Oct 19, 2013
  2. jcsd
  3. Oct 19, 2013 #2
    I am assuming p is prime. Do you agree that p divides p! and that p does not divide k! and that p does not divide (p-k)! ?

    If so, then p must divide p choose k since there are no factors of p in the denominator that would "cancel" the p in the numerator.

    As a side note, I would suggest not using the wedge things in a proof (or at all.) They are confusing.
     
  4. Oct 19, 2013 #3
    Agreed.
    I dont understand this.
    Ok thanks.
     
  5. Oct 19, 2013 #4

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    ##k## and ##(p-k)## are both less than ##p##.

    So, all the prime factors of ##k\,!## and of ##(p-k)!## are less than ##p##.

    ##p## is a prime, so ##p## can't divide a number whose prime factors are all less than ##p##.
     
  6. Oct 19, 2013 #5
    Doesnt this imply that p does not divide p choose k?
     
  7. Oct 19, 2013 #6
    It means that p divides the numerator of the fraction but not the denominator. So, p divides the fraction.
     
  8. Oct 19, 2013 #7
    Ah of course, thank you.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Lemma Lucas theorem
  1. Urysohn lemma? (Replies: 14)

  2. Interesting lemma (Replies: 15)

Loading...