[SOLVED] Divisibility property of a prime's central binomial coefficient

**russel** · September 27th 2009, 08:41 AM

Hello there,
It's the first time I am posting and I think it is a worth mentioning problem.

Here it is:

Prove that the central binomial coefficient of a prime number when divised by the prime's second power gives as remainder two. In other (more mathematical) words:
${2p\choose p}=2\mod{p^2}$

**Bruno J.** · September 27th 2009, 10:02 AM

$\frac{(2p)!}{(p!)^2} = \frac{(p+1)(p+2)...(2p-1)(2p)}{p!}= \frac{(p+1)(p+2)...(2p-1)(2)}{p-1!}$

$\equiv \frac{-1}{-1}2 \equiv 2 \mod p$

by Wilson's theorem.

**Bruno J.** · September 27th 2009, 10:05 AM

Oh sorry I didn't notice the $p^2$ . Well at least that's a first step

**russel** · September 27th 2009, 11:33 AM

I can't find the solution yet... Thanks for trying... That was one of the questions of a pregraduate Discrete Mathematics exam and I thought it was easy enough to solve it. But now, I suppose it is NOT!

If I expand the factorial I'm getting this:
$2 \times \frac{(p+1)(p+2)...(2p-1)}{(p-1)(p-2)...(p-p+1)}$
Should I search for a connection between $p+1$ and $p-1$ equivalent $\mod{p^2}$ ? and prove something like $2 \times \frac{-1}{-1} \equiv 2 \mod{p^2}$

**Bruno J.** · September 28th 2009, 10:58 AM

Here is the complete proof :

$<br /> \frac{(2p)!}{(p!)^2} = \frac{(p+1)(p+2)...(2p-1)(2p)}{p!}= 2\frac{(p+1)(p+2)...(2p-1)}{p-1!}$

$= 2\frac{(p+1)(p+2)...(p+(p-1))}{p-1!} \times \frac{(p-1)(p-2)...(p-(p-1))}{(p-1)(p-2)...(p-(p-1))}$

$\equiv 2\frac{(p^2-1^2)(p^2-2^2)...(p^2-(p-1)^2)}{((p-1)!)^2} \equiv 2 \frac{(-1)^{p-1}((p-1)!)^2}{((p-1)!)^2} \equiv (-1)^{p-1}2 \mod p^2$

So when $p$ is odd, $\frac{(2p)!}{(p!)^2} \equiv (-1)^{p-1}2 \equiv 2 \mod p^2$ .

If $p=2$ then

$\frac{(2p)!}{(p!)^2} \equiv -2 \equiv 2 \mod 4$

so the theorem holds for all primes.

**russel** · September 28th 2009, 12:55 PM

I did this (multiplying by $\frac{(p-1)!}{(p-1)!}$ ) but then I couldn't figure out the next step, the congruence. Thanks again Bruno! Finally, it was obvious!

**Bruno J.** · September 28th 2009, 04:16 PM

It's always obvious once it's proven!

You are welcome Russel.

Thread: [SOLVED] Divisibility property of a prime's central binomial coefficient

LinkBack

Thread Tools

Display

[SOLVED] Divisibility property of a prime's central binomial coefficient

Thanks man

Thanks a lot

Similar Math Help Forum Discussions

Prime Divisibility Proof

Divisibility of central binomial coefficient

A divisibility property

Divisibility by prime

Binomial Theorem or Binomial Coefficient

Search Tags