congruence help

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

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

...

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:

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