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

[katatonia]

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.

 

[Hurkyl]

What is "the combination"?

 

[shmoe]

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.

 

[katatonia]

combination(p-1, k) = [(p-1)!]/ [k!*(p-1-k)!]

sorry if i didn't make sense :)

 

[Hurkyl]

In other words...

<br /> \binom{p-1}{k} = \frac{p-1}{1} \frac{p-2}{2} \cdots \frac{p-k}{k}<br />

...

 

[robert Ihnot]

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:

\frac{(p-1)!}{0!(p-1)!} =1=(-1)^0