3
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ $(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$. $\endgroup$ – Anurag A Jun 1 '14 at 23:50
  • $\begingroup$ Careful. $(2p)! = (2p) \cdot (2p - 1) \cdot (2p - 2) ... \cdot 4 \cdot 3 \cdot 2$. $\endgroup$ – Kaj Hansen Jun 1 '14 at 23:50
  • $\begingroup$ You seem to have confused the factorial with the double factorial. $\endgroup$ – Lucian Jun 2 '14 at 6:19
  • $\begingroup$ Lucas' theorem gives this result immediately, and is nice to know about anyway. $\endgroup$ – Jyrki Lahtonen Jun 2 '14 at 19:16
8
$\begingroup$

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$.

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

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$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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