Results 1 to 7 of 7

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

  1. #1
    Newbie
    Joined
    Sep 2009
    From
    Athens, Greece
    Posts
    20

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

    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}
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    \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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Oh sorry I didn't notice the p^2. Well at least that's a first step
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2009
    From
    Athens, Greece
    Posts
    20

    Thanks man

    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}
    Last edited by russel; September 28th 2009 at 03:52 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Sep 2009
    From
    Athens, Greece
    Posts
    20

    Thanks a lot

    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!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    It's always obvious once it's proven!

    You are welcome Russel.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime Divisibility Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 25th 2011, 09:04 AM
  2. Divisibility of central binomial coefficient
    Posted in the Number Theory Forum
    Replies: 18
    Last Post: July 11th 2010, 08:43 PM
  3. A divisibility property
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 30th 2010, 11:44 AM
  4. Divisibility by prime
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: April 16th 2010, 09:57 AM
  5. Binomial Theorem or Binomial Coefficient
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: October 2nd 2009, 01:06 PM

Search Tags


/mathhelpforum @mathhelpforum