Lemma Lucas theorem

  • Thread starter Max.Planck
  • Start date
  • #1
129
0

Main Question or Discussion Point

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:

Answers and Replies

  • #2
828
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.
 
  • #3
129
0
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)! ?
Agreed.
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.
I dont understand this.
As a side note, I would suggest not using the wedge things in a proof (or at all.) They are confusing.
Ok thanks.
 
  • #4
AlephZero
Science Advisor
Homework Helper
6,994
291
##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##.
 
  • #5
129
0
##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##.
Doesnt this imply that p does not divide p choose k?
 
  • #6
828
2
It means that p divides the numerator of the fraction but not the denominator. So, p divides the fraction.
 
  • Like
Likes 1 person
  • #7
129
0
It means that p divides the numerator of the fraction but not the denominator. So, p divides the fraction.
Ah of course, thank you.
 

Related Threads on Lemma Lucas theorem

  • Last Post
Replies
1
Views
684
Replies
1
Views
1K
Replies
4
Views
933
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
15
Views
4K
  • Last Post
Replies
14
Views
3K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
3
Views
1K
Top