# Lemma Lucas theorem

1. Oct 19, 2013

### 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: Oct 19, 2013
2. Oct 19, 2013

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

3. Oct 19, 2013

### Max.Planck

Agreed.
I dont understand this.
Ok thanks.

4. Oct 19, 2013

### AlephZero

$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. Oct 19, 2013

### Max.Planck

Doesnt this imply that p does not divide p choose k?

6. Oct 19, 2013

### Robert1986

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

7. Oct 19, 2013

### Max.Planck

Ah of course, thank you.