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.

PROBLEM: Let p be a prime number. Show that the binomial coefficient $\binom{2p}{p}$ is congruent to $2$ mod p.

POSSIBLE SOLUTION

$\binom{2p}{p}=\frac{(2p)!}{p!(2p-p)!}=\frac{(2p)!}{p!p!}=\frac{2*4*..*2p}{p!p!}=\frac{2(1*2*..*p)}{p!p!}=\frac{2*p!}{p!p!}=\frac{2}{p!} \equiv 2 \mod p$

I am unsure of my last step. Can someone tell me if I am correct or not?

share|improve this question
6  
$(2p)!=1 \cdot 2 \cdot 3 \cdot 4 \dotsb (2p-1) \cdot 2p$. That is where you have made the first error. The second error is where you made $p!$ disappear in the last step. Note that $p! \equiv 0 \pmod{p}$, hence not invertible modulo $p$. –  Anurag A Jun 1 at 23:50
    
Careful. $(2p)! = (2p) \cdot (2p - 1) \cdot (2p - 2) ... \cdot 4 \cdot 3 \cdot 2$. –  Kaj Hansen Jun 1 at 23:50
    
You seem to have confused the factorial with the double factorial. –  Lucian Jun 2 at 6:19
    
Lucas' theorem gives this result immediately, and is nice to know about anyway. –  Jyrki Lahtonen Jun 2 at 19:16

3 Answers 3

up vote 7 down vote accepted

An alternative proof is to use the good old identity

$$\binom{2p}{p}=\sum_{j=0}^p\binom{p}{j}^2,$$

and to note that $\binom{p}{j}\equiv 0\pmod{p}$ for $0<j<p$ and $\equiv 1\pmod{p}$ for $j=0,p$.

share|improve this answer
    
Note you proved it is $=0\mod p^2$, unless I am missing something. –  Pedro Tamaroff Jun 2 at 0:05
1  
@PedroTamaroff I think it proves that (in addition) $\binom{2p}{p}\equiv 2\pmod{p^2}$, doesn't it? –  mathse Jun 2 at 0:08
1  
Yes, that's what I mean. =) –  Pedro Tamaroff Jun 2 at 0:12

When one does number theory, "fractions" can easily lead to error, it is better to keep things "flat." Let $w=\binom{2p}{p}$. Then $$(2p)!=wp!p!.$$ Note that $(2p)!=(2p)(2p-1)(2p-2)\cdots (p+1)p!$. Substituting, and doing a bit of cancelling, we get $$(2)(p+1)(p+2)\cdots (2p-1)=w(p-1)!.$$ But note that $(p+1)(p+2)\cdots (2p-1)\equiv (p-1)!\pmod{p}$. Since $(p-1)!\not\equiv 0\pmod{p}$, we can cancel, and obtain $w\equiv 2\pmod{p}$.

Remark: The solution by mathse is nicer, and yields immediately the improved congruence $\binom{2p}{p}\equiv 2\pmod{p^2}$. This is also obtainable with the approach above. The result holds for $p=2$. And when $p\gt 2$, the product $(p+1)(p+2)\cdots (2p-1)$ is congruent to $(1)(2)\cdots(p-1)$ modulo $p^2$. For imagine multiplying out $(p+1)(p+2)\cdots (p+p-1)$. We get some terms that involve powers of $p\ge 2$, and the term $p(1+2+\cdots +(p-1))$, and finally the term $(1)(2)\cdots(p-1)$. If $p$ is odd, then $1+2+\cdots +(p-1)$ is divisible by $p$

share|improve this answer

First verify that it's true for the only even prime $2$.

$\displaystyle \binom{4}{2} = 6 \equiv 2 \pmod 2$

That leaves you to prove it only for odd prime $p$.

$\displaystyle \binom{2p}{p} = \frac{(2p)!}{p!p!} = \frac{(2p)(2p-1)...(2)(1)}{p!(p)(p-1)...(2)(1)}$

Cancelling terms, we get:

$\displaystyle \frac{(2p)(2p-1)...(p+1)}{p!} = \frac{(2p)(2p-1)...[2p-(p-1)]}{p!} = 2\frac{(2p-1)...[2p-(p-1)]}{(p-1)!}$

Working $\mod p$, the expression becomes:

$\displaystyle 2\frac{(-1)(-2)...[-(p-1)]}{(p-1)!}$

Since $p$ is an odd prime, there are an even number of terms in the numerator, so the expression is:

$\displaystyle 2\frac{(p-1)!}{(p-1)!} = 2$

Hence $\displaystyle \binom{2p}{p} \equiv 2 \pmod{p}$, as required.

share|improve this answer

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.