Thread Closed

congruence help

 
Share Thread
Apr6-05, 08:23 PM   #1
 

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
Apr6-05, 09:01 PM   #2
 
Recognitions:
Gold Membership Gold Member
Science Advisor Science Advisor
Retired Staff Staff Emeritus
What is "the combination"?
Apr6-05, 10:59 PM   #3
 
Recognitions:
Homework Helper Homework Help
Science Advisor 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.
Apr7-05, 12:44 AM   #4
 

congruence help


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

sorry if i didn't make sense :)
Apr7-05, 07:13 AM   #5
 
Recognitions:
Gold Membership Gold Member
Science Advisor Science Advisor
Retired Staff Staff Emeritus
In other words...

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

...
Apr8-05, 08:08 PM   #6
 
Recognitions:
Gold Membership 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:

[tex]\frac{(p-1)!}{0!(p-1)!} =1=(-1)^0 [/tex]
Thread Closed

Similar discussions for: congruence help
Thread Forum Replies
Congruence difficulty Linear & Abstract Algebra 1
Congruence - subject difficulty General Math 0
Solving a congruence Calculus & Beyond Homework 2
Congruence Precalculus Mathematics Homework 3
solution to the general congruence Linear & Abstract Algebra 2