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}$.

- Dec 29th 2009, 04:46 AMjames_bond# 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}$.

- Dec 29th 2009, 06:05 PMabender
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. - Dec 31st 2009, 07:13 AMjames_bond
- Dec 31st 2009, 11:10 PMabender
- Jan 1st 2010, 01:03 AMjames_bond
- Jan 1st 2010, 01:59 AMabender
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.