1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...