Understand Lemma Lucas Theorem & Its Proof

[Max.Planck]

Hi. I don't 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?

 

[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 don't 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.

 

[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$.

 

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

 

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