# Congruence help

1. Apr 6, 2005

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

2. Apr 6, 2005

### Hurkyl

Staff Emeritus
What is "the combination"?

3. Apr 6, 2005

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

4. Apr 7, 2005

### katatonia

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

sorry if i didn't make sense :)

5. Apr 7, 2005

### Hurkyl

Staff Emeritus
In other words...

$$\binom{p-1}{k} = \frac{p-1}{1} \frac{p-2}{2} \cdots \frac{p-k}{k}$$

...

6. Apr 8, 2005

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