## congruence help

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.
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity
 Recognitions: Gold Member Science Advisor Staff Emeritus What is "the combination"?
 Recognitions: Homework Help Science Advisor 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.

## congruence help

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

sorry if i didn't make sense :)
 Recognitions: Gold Member Science Advisor Staff Emeritus In other words... $$\binom{p-1}{k} = \frac{p-1}{1} \frac{p-2}{2} \cdots \frac{p-k}{k}$$ ...
 Recognitions: Gold Member 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$$

 Similar discussions for: congruence help Thread Forum Replies Linear & Abstract Algebra 1 General Math 0 Calculus & Beyond Homework 2 Precalculus Mathematics Homework 3 Linear & Abstract Algebra 2