Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Congruence help

  1. Apr 6, 2005 #1
    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. jcsd
  3. Apr 6, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What is "the combination"?
     
  4. Apr 6, 2005 #3

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. Apr 7, 2005 #4
    combination(p-1, k) = [(p-1)!]/ [k!*(p-1-k)!]

    sorry if i didn't make sense :)
     
  6. Apr 7, 2005 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    In other words...

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

    ...
     
  7. Apr 8, 2005 #6
    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]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Congruence help
  1. Congruence Solving (Replies: 6)

  2. Congruence relation (Replies: 0)

Loading...