Proving Congruence: (p-1, k) ≡ (-1)^k (mod p)

  • Context: Undergrad 
  • Thread starter Thread starter katatonia
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around proving the congruence of the binomial coefficient (p-1, k) with (-1)^k modulo p for each odd prime p and for k in the range 0 to p-1. The scope includes mathematical reasoning and exploration of combinatorial identities.

Discussion Character

  • Mathematical reasoning, Exploratory

Main Points Raised

  • One participant seeks assistance in proving the congruence relation involving the binomial coefficient and a power of -1.
  • Another participant questions the meaning of "the combination," suggesting a need for clarification.
  • A participant proposes that "the combination" refers to the binomial coefficient and suggests using the binomial theorem and Fermat's little theorem to approach the problem.
  • A clarification is provided on the definition of the binomial coefficient, including its formula.
  • Further elaboration on the binomial coefficient is given, showing its expression in terms of products.
  • A later reply indicates that induction may be a method to prove the statement, providing a basis case for k=0.

Areas of Agreement / Disagreement

Participants have not reached a consensus on the proof method, and multiple approaches are being discussed, including induction and the use of binomial expansion.

Contextual Notes

There are unresolved assumptions regarding the application of induction and the completeness of the proposed methods. The discussion does not clarify all mathematical steps involved in the proof.

katatonia
Messages
2
Reaction score
0
Anybody know how to do this one:

For each odd prime p and for each k such that 0<= k <=(p-1), prove that:

the combination (p-1, k) is congruent to (-1)^k (mod p)




Any help would be great.
 
Physics news on Phys.org
What is "the combination"?
 
I'm guessing the 'combination' is referring to the binomial coefficient.

In that case consider (x+y)^p mod p. Expand/simplify it in a couple ways, using the fact that p is prime (Fermat's little theorem) and then using the binomial theorem on (x+y)(x+y)^(p-1). Then compare coefficients.
 
combination(p-1, k) = [(p-1)!]/ [k!*(p-1-k)!]

sorry if i didn't make sense :)
 
In other words...

[tex] \binom{p-1}{k} = \frac{p-1}{1} \frac{p-2}{2} \cdots \frac{p-k}{k}[/tex]

...
 
Going back to the originial question, Does anybody know how to do this one? The answer is that you use induction. The basis will work for 0 giving:

[tex]\frac{(p-1)!}{0!(p-1)!} =1=(-1)^0[/tex]
 

Similar threads

  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 17 ·
Replies
17
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
Replies
48
Views
7K
  • · Replies 40 ·
2
Replies
40
Views
5K
  • · Replies 4 ·
Replies
4
Views
4K
  • · Replies 31 ·
2
Replies
31
Views
4K
  • · Replies 25 ·
Replies
25
Views
5K
  • · Replies 21 ·
Replies
21
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K