Results 1 to 6 of 6

Math Help - Binomial Coefficient

  1. #1
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163

    Binomial Coefficient

    For a prime  \displaystyle p , show  \displaystyle \binom{ap}{bp} \equiv \binom{a}{b} \bmod{p^2} .
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    715
    I try not to consider the fact  \binom{n}{k} = \frac{ n!}{ k! (n-k)! } , i just regard it as the coefficient of a term in  (1+x)^n

    We know  \binom{ap}{bp} is the coefficient of  x^{bp} in the expansion of  (1+x)^{ap} while  \binom{a}{b} is the coefficient of  x^{bp} in the expansion of  (1+x^p)^a . Therefore ,  \binom{ap}{bp} - \binom{a}{b} is the coefficient of  x^{bp} of  (1+x)^{ap} - (1+x^p)^a .


    I would like to show that all the terms that the degrees are the multiple of prime  p are congruent to zero modulo  p^2 .

    I consider  (1+x)^{ap} - (1+x^p)^a = [ (1+x)^p ]^a - [(1+x^p)]^a

     = [(1+x)^p - 1 - x^p ] [ (1+x)^{p(a-1)} + (1+x)^{p(a-2)} ( 1 + x^p) + ... + (1+x)^p ( 1 + x^p)^{a-2} + (1+x^p)^{a-1} ]

    Note that all the terms in  (1+x)^p - 1 - x^p are divisible by p .

    Then i consider the second polynomial , the annoying one .

     P(x) = (1+x)^{p(a-1)} + (1+x)^{p(a-2)} ( 1 + x^p) + ... + (1+x)^p ( 1 + x^p)^{a-2} + (1+x^p)^{a-1}

    I use the fact  (1+x)^p \equiv 1+ x^p \bmod{p} to simplify  P(x) :

     P(x) = (1+x^p)^{a-1} + (1+x^p)^{a-2} ( 1+ x^p ) + ... (1+x^p)(1+x^p)^{a-2} + (1+x^p)^{a-1} + p F(x)

     = a ( 1+ x^p )^{a-1} + p F(x)

    Then we are done , haha , let's get back the first polynomial  (1+x)^p - 1 - x^p = \binom{p}{1}x + \binom{p}{2} x^2 + ... + \binom{p}{p-1} x^{p-1} whose degree ranges from  1 to  p-1 so they are prime to  p . Consider  a(1+x^p)^{a-1} , we find that the degrees are all mutiple of  p so they become useless in the expansion if we are evaluating the coefficient of  x^{bp} since no terms in  (1+x)^p - 1 - x^p could make the 'connection' to them . Therefore , the coefficient we are considering ( of  x^{bp} ) is necessarily the mutiple of  p^2 , one  p from  (1+x)^p - 1 - x^p and one from  p F(x) .

    Remarks :

    I don't like this result ... i am going to show that

    For a prime  p \geq 5 we always have

     \binom{ap}{bp} \equiv \binom{a}{b} \bmod{p^3} :

    Let's check my solution , write  A = (1+x)^p - 1 - x^p or  (1+x)^p = 1 + x^p + A

     P(x) \equiv [ ( 1+ x^p )^{a-1}  + (1+x^p)^{a-2} (a-1) A]  + [ ( 1+ x^p )^{a-1}  + (1+x^p)^{a-2} (a-2) A ] +  ... +  [( 1+ x^p )^{a-1}  + (1+x^p)^{a-2}  A ] + (1+x^p)^{a-1} \bmod{p^2}

     \equiv a(1+x^p)^{a-1} + A(1+x^p)^{a-2} ~ [ 1+ 2+3+...+ (a-1) ] \bmod{p^2}

     \equiv a(1+x^p)^{a-1} + [(1+x)^p - 1 - x^p ] (1+x^p)^{a-2} \cdot \frac{a(a-1)}{2} \bmod{p^2} ~~~~ a > 1


    Then the coefficient of  x^{bp} in  P(x) is congruent to (  \bmod{p^3} ) that in   [(1+x)^p - 1 - x^p ]^2 (1+x^p)^{a-2} \cdot \frac{a(a-1)}{2}  . It suffices to show that the coefficient of  x^{p} in [(1+x)^p - 1 - x^p ]^2 is congruent to zero modulo  p^3 .

    ie :

     \binom{p}{1}^2 + \binom{p}{2}^2 + ... + \binom{p}{p-1}^2 = \binom{2p}{p} - 2 \equiv 0 \bmod{p^3} .

    Please see this post , http://www.mathhelpforum.com/math-he...nt-149645.html
    It is not a help begging but a challenge , let's finish the proof by solving my challenge .
    Last edited by simplependulum; August 11th 2010 at 06:04 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    let f(x)=\prod_{k=1}^{p-1}(x-k)=x^{p-1}-a_1x^{p-2} + \cdots -a_{p-2}x + a_{p-1}. by the Fermat's little theorem, in (\mathbb{Z}/p\mathbb{Z})[x], we have f(x)=x^{p-1}-1.

    as a result (p-1)!=a_{p-1} \equiv -1 \mod p, which is Wilson's theorem, and a_j \equiv 0 \mod p, for all j \neq p-1. in particular f(np) \equiv -1 \mod p^2, for any integer n.

    thus f(ap)f((a-1)p) \cdots f((a-b+1)p) \equiv (-1)^b \mod p^2 and  f(bp)f((b-1)p) \cdots f(p) \equiv (-1)^b \mod p^2. the result now follows from the trivial identity

    \displaystyle \binom{ap}{bp}=\binom{a}{b} \frac{f(ap)f((a-1)p) \cdots f((a-b+1)p)}{f(bp)f((b-1)p) \cdots f(p)}.

    simplependulum's question is also solved by this method and using an old result due to Wolstenholmes which says that for p>3: \ a_{p-2} \equiv 0 \mod p^2.

    thus f(np) \equiv -1 \mod p^3 for all integers n. therefore for all primes p > 3 and all integers a,b we have \displaystyle \binom{ap}{bp} \equiv \binom{a}{b} \mod p^3.
    Last edited by NonCommAlg; August 11th 2010 at 09:36 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    715
    simplependulum's question is also solved by this method and using an old result due to Wolstenholmes which says that for p>3: \ a_{p-2} \equiv 0 \mod p^2.

    thus f(np) \equiv -1 \mod p^3 for all integers n. therefore for all primes p > 3 and all integers a,b we have \displaystyle \binom{ap}{bp} \equiv \binom{a}{b} \mod p^3.
    Yeah , the key is :

    For  p \geq 5

     \frac{1}{1} + \frac{1}{2} + ... + \frac{1}{p-1} \equiv 0 \bmod{p^2}

    Proof :

    Assume  p \neq 2~,~ 3

     \sum_{k=1}^{p-1} \frac{1}{k} = \ \sum_{k=1}^{(p-1)/2} \left[ \frac{1}{p-k} + \frac{1}{k} \right]

     = p \sum_{k=1}^{(p-1)/2} \frac{1}{k(p-k)}

    so we are going to show  \sum_{k=1}^{(p-1)/2} \frac{1}{k(p-k)} \equiv 0 \bmod{p} we have

     \sum_{k=1}^{(p-1)/2} \frac{1}{k(p-k)} \equiv -\sum_{k=1}^{(p-1)/2} \frac{1}{k^2}  \equiv - \sum_{k=1}^{(p-1)/2} k^2  \equiv - \frac{p(p^2-1)}{24} \equiv 0 \bmod{p}

    Therefore , \frac{1}{1} + \frac{1}{2} + ... + \frac{1}{p-1} \equiv 0 \bmod{p^2}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    An attempt proof.

    For any integer r let I_r=(rp+1)(rp+2)\cdots(rp+p-1), then (*) I_r\equiv (p-1)!\bmod p^2; this will be justified later.
    With this we can write for some positive integer k the following: (kp)!=I_0\cdot I_1\cdots I_{k-1}\cdot(1p)(2p)\cdots(kp)=I_0\cdot I_1\cdots I_{k-1}\cdot p^kk!, and so
    (^) \displaystyle{\frac{(kp)!}{p^kk!}=I_0\cdot I_1\cdots I_{k-1}\equiv [(p-1)!]^k\bmod p^2} (I applied the congruence (*)).

    Set c=a-b for brevity, so \displaystyle{A=\binom{ap}{bp}=\frac{(ap)!}{(bp)!(  cp)!}} and \displaystyle{B=\binom{a}{b}=\frac{(a)!}{(b)!(c)!}  }. Consider the following \displaystyle{A\frac{(bp)!}{p^bb!}\frac{(cp)!}{p^c  c!}=A\frac{(bp)!(cp)!}{p^ab!c!}=\frac{(ap)!}{p^ab!  c!}=\frac{(ap)!}{p^aa!}B}, the last equality is because b!c!B=a! . I write the main equality: (#) \displaystyle{A\frac{(bp)!}{p^bb!}\frac{(cp)!}{p^c  c!}=\frac{(ap)!}{p^aa!}B}

    Now computing (#) modulo p^2 and using result (^) we have A[(p-1)!]^b[(p-1)!]^c\equiv [(p-1)!]^aB\bmod p^2; A[(p-1)!]^a\equiv [(p-1)!]^aB\bmod p^2. Since [(p-1)!]^a is relatively prime to p^2 , we can arrive at A\equiv B\bmod p^2 , or \displaystyle \binom{ap}{bp} \equiv \binom{a}{b} \bmod{p^2}.

    Everything depends now on proving (*). From the expansion of I_r it can be noticed that taking rp from more than one parentheses gives terms that are divisble by p^2 , therefore I_r\equiv rp\cdot t+(p-1)!\bmod p^2, where t=\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\cdots+\frac{(p-1)!}{p-1}.

    Consider the polynomial P(x)=(x-1)(x-2)\cdots(x-(p-1)). Then, P(x)=x^{p-1}-s_{p-2}x^{p-2}+\cdots-s_1x^1+s_0, where s_1=t, s_0=(p-1)!. P(p)\equiv -s_1p+s_0=-tp+(p-1)!\bmod p^2 and because P(p)=(p-1)! we have (p-1)!\equiv -tp+(p-1)! \bmod p^2; or tp\equiv 0 \bmod p^2. Divide by p , so t\equiv 0\bmod p, and rp\cdot t is divisible by p^2 .

    We now can conclude that I_r\equiv (p-1)! \bmod p^2.

    I hope I'm not missing something...
    Last edited by melese; August 12th 2010 at 06:37 PM. Reason: (^) refers to equation
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    We proceed by induction on a, for a = 0 it's trivial that \binom{a\cdot p}{b \cdot p} \equiv_{p^2} \binom{a}{b} for all b\in \mathbb{N}.

    Now assume the assertion holds for a-1, let's show it the holds for a. - in what follows we consider a > b since it's trivial otherwise.

    We have \binom{a\cdot p}{b \cdot p} = \binom{(a-1)\cdot p + p}{b\cdot p} = \sum_{k=0}^{p} \binom{(a-1)\cdot p}{b\cdot p - k}\cdot \binom{p}{k}=\sum_{k=1}^{p-1}\binom{(a-1)\cdot p}{b\cdot p - k}\cdot \binom{p}{k}+\binom{(a-1)\cdot p}{b\cdot p}+\binom{(a-1)\cdot p}{(b-1)\cdot p}

    Note that if p divides \sum_{k=1}^{p-1}\binom{(a-1)\cdot p}{b\cdot p - k}\cdot \binom{p}{k} we are done, because \binom{(a-1)\cdot p}{b\cdot p}+\binom{(a-1)\cdot p}{(b-1)\cdot p} \equiv _{p^2} {\binom{a-1}{b}+\binom{a-1}{b-1}=\binom{a}{b} } by the inductive hypothesis and Pascal's identity.

    Now \binom{(a-1)\cdot p}{b\cdot p - k} = \frac{((a-1)\cdot p)!}{((a-1-b)\cdot p + k)!\cdot (b\cdot p - k)!} . If we denote by v_p(n) the greatest integer r such that p^r |n! then:
    v_p((a-1)\cdot p) = (a-1) + v_p(a-1) ;
    v_p((a-1-b)\cdot p + k) = v_p(a-1-b) + a-1-b since 0<k<p ;
    v_p(b\cdot p - k) = v_p(b) + b  - e_p(b\cdot p) where e_p(n) is the greatest r such that p^r|n since p>k>0 - you can check this by using Polignac's formula -

    Thus e_p\left(\binom{(a-1)\cdot p}{b\cdot p - k}\right) = e_p\left(\binom{a-1}{b}\right)  + e_p(b\cdot p)\geq 1 and so p divides \binom{(a-1)\cdot p}{b\cdot p - k} for all k = 1,...,p-1 .

    But also \binom{p}{k} is a multiple of p for k = 1, ..., p-1 and so we are done \square
    Last edited by PaulRS; October 11th 2010 at 01:15 PM. Reason: Fixing an error.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sum with binomial coefficient
    Posted in the Calculus Forum
    Replies: 4
    Last Post: August 11th 2011, 11:00 AM
  2. binomial coefficient.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 12th 2010, 10:30 PM
  3. Binomial Coefficient
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2009, 05:37 PM
  4. Binomial Theorem or Binomial Coefficient
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: October 2nd 2009, 01:06 PM
  5. Binomial Coefficient
    Posted in the Pre-Calculus Forum
    Replies: 16
    Last Post: April 9th 2008, 07:13 PM

Search Tags


/mathhelpforum @mathhelpforum