Understand Lemma Lucas Theorem & Its Proof

  • Thread starter Max.Planck
  • Start date
  • Tags
    Theorem
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.
  • #1
129
0
Hi. I don't understand the following proof.
Lemma
Let p be a prime number and 1<=k<=p-1, then:
[itex]{p \choose k} \equiv 0 \pmod{p}[/itex]

Proof

[itex]{p \choose k} = \frac{p!}{k!(p-k)!}[/itex]. Since [itex]p | p![/itex] but [itex] p \not | k! \land p \not | (p-k)![/itex] 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:
Physics news on Phys.org
  • #2
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
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.
 
  • #4
##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
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?
 
  • #6
It means that p divides the numerator of the fraction but not the denominator. So, p divides the fraction.
 
  • Like
Likes 1 person
  • #7
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.

Suggested for: Understand Lemma Lucas Theorem & Its Proof

Replies
4
Views
852
Replies
21
Views
1K
Replies
2
Views
393
Replies
11
Views
995
Replies
3
Views
838
Replies
2
Views
1K
Back
Top