Comparing Corresponding Factors
Date: 03/04/2003 at 23:40:48 From: John Mark Subject: Fermat's Theorem If p is an odd prime and k is an integer satisfying 1 <= k <= p-1, show that the binomial coefficient ((p-1) k) is congruent to (-1)^k(mod p) I realize that binomial coefficient (p k) is congruent to 0 mod p. I'm assuming that the statement has to do with a factorization of the binomial coefficient, but I can not see how to factor it and complete the proof.
Date: 03/05/2003 at 03:50:15 From: Doctor Jacques Subject: Re: Fermat's Theorem Hi John, We can write the binomial coefficient C(p-1,k) as: C(p-1,k) = ((p-1)*...*(p-k))/(1*...*k) We must show that this is congruent to (-1)^k mod p. As p is prime, and no factor of the denominator is divisible by p, this is equivalent to: (p-1)*...*(p-k) = (-1)^k * (1*...*k) mod p Notice that both products contain k factors. If you compare corresponding factors modulo p, this should give you a good hint... Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum