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

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

2. 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.

3. Originally Posted by abender
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)?

4. Originally Posted by james_bond
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.}$

5. Originally Posted by abender
Let $\displaystyle n \in \mathbb{Z}^{+} \text{ and } p \text{ be a prime number.}$
OK...

6. Originally Posted by james_bond
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.