# Understand Lemma Lucas Theorem & Its Proof

• Max.Planck
In summary, the lemma states that for any prime number p and any integer k between 1 and p-1, the binomial coefficient p choose k will always be divisible by p. This is proven by showing that the prime factorization of p does not divide the denominator of the fraction, making p a factor of the entire fraction.

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

Last edited:
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.

Robert1986 said:
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.
Robert1986 said:
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.
Robert1986 said:
As a side note, I would suggest not using the wedge things in a proof (or at all.) They are confusing.
Ok thanks.

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

AlephZero said:
##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
Robert1986 said:
It means that p divides the numerator of the fraction but not the denominator. So, p divides the fraction.

Ah of course, thank you.

## 1. What is Lemma Lucas Theorem?

Lemma Lucas Theorem is a mathematical theorem that states the relationship between the binomial coefficients and the prime factors of their corresponding numbers. It is a special case of the more general Lucas's theorem.

## 2. What is the proof for Lemma Lucas Theorem?

The proof for Lemma Lucas Theorem is based on the properties of prime numbers, binomial coefficients, and modular arithmetic. It involves using the binomial theorem and the definition of prime factorization to show the relationship between the two.

## 3. What are the applications of Lemma Lucas Theorem?

Lemma Lucas Theorem has applications in number theory, combinatorics, and cryptography. It is used to solve problems related to binomial coefficients and prime numbers, such as finding the number of ways to choose objects from a set or determining the divisibility of a number.

## 4. Is Lemma Lucas Theorem a difficult concept to understand?

While the proof for Lemma Lucas Theorem may seem complex, the concept itself is not difficult to understand. It is based on basic principles of number theory and can be easily grasped with some knowledge of binomial coefficients and prime numbers.

## 5. Are there any variations of Lemma Lucas Theorem?

Yes, there are variations of Lemma Lucas Theorem that involve different types of numbers, such as Lucas numbers or Fibonacci numbers. These variations have their own proofs and applications, but they all share the same basic concept of relating binomial coefficients to prime factors.