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.