Results 1 to 6 of 6

Thread: # 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: $\displaystyle \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
    339
    Thanks
    46
    Hint: Write $\displaystyle n $ in the base 3 and let {$\displaystyle n_i$} be the digits which appear. The number of binomial coefficients not divisible by 3 is then given by $\displaystyle \Pi (n_i + 1) $ .


    Note that this works for any prime $\displaystyle 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 $\displaystyle n $ in the base 3 and let {$\displaystyle n_i$} be the digits which appear. The number of binomial coefficients not divisible by 3 is then given by $\displaystyle \Pi (n_i + 1) $ .


    Note that this works for any prime $\displaystyle 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
    339
    Thanks
    46
    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: $\displaystyle \tbinom {n}{0}, \tbinom {n}{1} , \tbinom {n}{2}, \ldots , \tbinom {n}{n}$.
    Let $\displaystyle
    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 $\displaystyle
    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
    339
    Thanks
    46
    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: $\displaystyle \tbinom {n}{0}, \tbinom {n}{1} , \tbinom {n}{2}, \ldots , \tbinom {n}{n}$.
    Let $\displaystyle
    n \text{ be a nonnegative integer and let } p \text{ be a prime number.}$

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

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

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

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

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

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

    Then, we have

    $\displaystyle
    (1+x)^n = (1+x)^{n_0} (1+x)^{n_1p} \cdot\cdot\cdot (1+x)^{n_{m}p^m} \equiv
    (1+x)^{n_0} (1+x^p)^{n_1} \cdot\cdot\cdot (1+x^{p^m})^{n_m}
    $

    Then, when developing factors on the right-hand side, we get a sum of the factors $\displaystyle 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 $\displaystyle \prod_{i=0}^m (n_i + 1) $ of these factors, which means that the number of binomial coefficients not divisible by p is $\displaystyle \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: Feb 20th 2013, 09:32 AM
  2. Replies: 8
    Last Post: Jul 3rd 2011, 03:55 PM
  3. Replies: 1
    Last Post: May 7th 2010, 11:49 PM
  4. Divisible by 16
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Feb 8th 2009, 08:03 AM
  5. Divisible
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 9th 2008, 11:16 PM

Search Tags


/mathhelpforum @mathhelpforum