Lemma Lucas theorem

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:
${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:

Related Linear and Abstract Algebra News on Phys.org
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.

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.

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

$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?

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

1 person
It means that p divides the numerator of the fraction but not the denominator. So, p divides the fraction.
Ah of course, thank you.