Results 1 to 6 of 6

Math Help - # of binomial coefficients not divisible by 3 is not divisible by 5

  1. #1
    Senior Member
    Joined
    Nov 2007
    Posts
    329

    # of binomial coefficients not divisible by 3 is not divisible by 5

    Show that the number of binomial coefficients not divisible by 3 is not divisible by 5 where the binomial coefficients are:  \tbinom {n}{0}, \tbinom {n}{1} ,  \tbinom {n}{2}, \ldots , \tbinom {n}{n}.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Mar 2008
    From
    Pennsylvania, USA
    Posts
    269
    Thanks
    37
    Hint: Write  n in the base 3 and let { n_i} be the digits which appear. The number of binomial coefficients not divisible by 3 is then given by  \Pi (n_i + 1) .


    Note that this works for any prime  p , not just 3.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2007
    Posts
    329
    Quote Originally Posted by abender View Post
    Hint: Write  n in the base 3 and let { n_i} be the digits which appear. The number of binomial coefficients not divisible by 3 is then given by  \Pi (n_i + 1) .


    Note that this works for any prime  p , not just 3.
    I see that it is true and it proves my question but can you (or somebody) show me why (proof)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Mar 2008
    From
    Pennsylvania, USA
    Posts
    269
    Thanks
    37
    Quote Originally Posted by james_bond View Post
    Show that the number of binomial coefficients not divisible by 3 is not divisible by 5 where the binomial coefficients are:  \tbinom {n}{0}, \tbinom {n}{1} ,  \tbinom {n}{2}, \ldots , \tbinom {n}{n}.
    Let <br />
n \in \mathbb{Z}^{+} \text{ and } p \text{ be a prime number.}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2007
    Posts
    329
    Quote Originally Posted by abender View Post
    Let <br />
n \in \mathbb{Z}^{+} \text{ and } p \text{ be a prime number.}
    OK...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Mar 2008
    From
    Pennsylvania, USA
    Posts
    269
    Thanks
    37
    Quote Originally Posted by james_bond View Post
    Show that the number of binomial coefficients not divisible by 3 is not divisible by 5 where the binomial coefficients are:  \tbinom {n}{0}, \tbinom {n}{1} ,  \tbinom {n}{2}, \ldots , \tbinom {n}{n}.
    Let <br />
n \text{ be a nonnegative integer and let } p \text{ be a prime number.}

    Let N(n,p) denote the number of binomial coefficients \binom{n}{a} \text{ that do not divide }p \text{, for all } a \in \{0,1,...,n\}.

    Now, assume that <br />
n \text{ is written in the base } p \text{ as } n = n_0 + n_1p + ... +n_mp^m whereby  0\leq n_j <p \text{ for all } j \in  \{0, 1, ..., m\}

    Now, we want to show that  N(n,p) = \prod_{i=0}^m (n_i + 1)

    It is obvious that   \binom{k}{p} \equiv 0 \mod p  , for all  k = \{1,2,...,p\}.

    As a result,  (1+x)^p \equiv 1+x^p \text{ in }(\mathbb{Z}/p\mathbb{Z})[x] .

    Then through induction, we show that <br />
(1+x)^{p^n} \equiv 1+x^{p^n} \text{ in } (\mathbb{Z}/p\mathbb{Z})[x] for any natural n.

    Then, we have

     <br />
(1+x)^n = (1+x)^{n_0} (1+x)^{n_1p} \cdot\cdot\cdot (1+x)^{n_{m}p^m} \equiv<br />
(1+x)^{n_0} (1+x^p)^{n_1} \cdot\cdot\cdot (1+x^{p^m})^{n_m}<br />

    Then, when developing factors on the right-hand side, we get a sum of the factors x^{b_0+b_1p+ \cdot\cdot\cdot + b_mp^m} , with a nonzero coefficient mod p. Now, since we can write any number uniquely in base p, all these factors are distinct and their coefficients mod 0 are nonzero. Thus, there are  \prod_{i=0}^m (n_i + 1) of these factors, which means that the number of binomial coefficients not divisible by p is  \prod_{i=0}^m (n_i + 1)

    Do your best to finish this.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: February 20th 2013, 10:32 AM
  2. Replies: 8
    Last Post: July 3rd 2011, 04:55 PM
  3. Replies: 1
    Last Post: May 8th 2010, 12:49 AM
  4. Divisible by 16
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 8th 2009, 09:03 AM
  5. Divisible
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 10th 2008, 12:16 AM

Search Tags


/mathhelpforum @mathhelpforum