# Lemma Lucas theorem

Max.Planck
Hi. I dont understand the following proof.

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

Proof

${p \choose k} = \frac{p!}{k!(p-k)!}$. Since $p | p!$ but $p \not | k! \land p \not | (p-k)!$ 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

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

Max.Planck
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.

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

Max.Planck
##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?

Robert1986
It means that p divides the numerator of the fraction but not the denominator. So, p divides the fraction.

1 person
Max.Planck
It means that p divides the numerator of the fraction but not the denominator. So, p divides the fraction.

Ah of course, thank you.