Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/