Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If $p$ is a prime number greater than 2 and $k\in \mathbb{N}$ so that $k < p$, how can I prove that $p\choose k$ is congruent to $0 \mod p$. I'm sorry I know my formatting is rough but I don't know how to format it correctly.

share|improve this question
1  
Note natural means $k \geq 1.$ This has probably been asked several times before, it's a standard and useful fact. –  Will Jagy Dec 5 '12 at 4:32
add comment

3 Answers

Hint: Do you know that ${p \choose k}=\frac {p!}{k!(p-k)!}?$

share|improve this answer
    
I do I'm having trouble with the congruency part of it, I haven't done congruences in a while and was shaky at best when I did do them. –  Jack Forest Dec 5 '12 at 4:42
    
@JackForest: If $p$ is prime how can there be it a factor of the denominator? –  Ross Millikan Dec 5 '12 at 4:43
    
There can not be a factor for the denominator since p is only divisible by 1 and itself. –  Jack Forest Dec 5 '12 at 4:46
    
@JackForest: spot on. Do you think $0 \in \mathbb N$? Then you need one more piece. –  Ross Millikan Dec 5 '12 at 4:50
    
0 is not ∈ N correct? –  Jack Forest Dec 5 '12 at 4:52
show 4 more comments

So, you have: $$\frac{p!}{k!(p-k)!}$$ and you want to prove this is a multiple of $p$.

Hint: $n! = n(n-1)!$

share|improve this answer
add comment

For $\,1\leq k\leq p-1\,$:

$$\binom{p}{k}=\frac{p!}{k!(p-k)!}=\frac{(k+1)(k+2)\cdot\ldots\cdot (p-1)}{1\cdot 2\cdot\ldots\cdot (p-k)}\cdot\;p$$

Since the binomial coefficient is an integer and all the factors both in the numerator and in the denominator above are smaller than $\,p\,$, we're done

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.