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

• December 29th 2009, 04:46 AM
james_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: $\tbinom {n}{0}, \tbinom {n}{1} , \tbinom {n}{2}, \ldots , \tbinom {n}{n}$.
• December 29th 2009, 06:05 PM
abender
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.
• December 31st 2009, 07:13 AM
james_bond
Quote:

Originally Posted by abender
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)?
• December 31st 2009, 11:10 PM
abender
Quote:

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: $\tbinom {n}{0}, \tbinom {n}{1} , \tbinom {n}{2}, \ldots , \tbinom {n}{n}$.

Let $
n \in \mathbb{Z}^{+} \text{ and } p \text{ be a prime number.}$
• January 1st 2010, 01:03 AM
james_bond
Quote:

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

OK...
• January 1st 2010, 01:59 AM
abender
Quote:

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: $\tbinom {n}{0}, \tbinom {n}{1} , \tbinom {n}{2}, \ldots , \tbinom {n}{n}$.

Let $
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 $
n \text{ is written in the base } p \text{ as } n = n_0 + n_1p + ... +n_mp^m$
whereby $0\leq n_j

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 $
(1+x)^{p^n} \equiv 1+x^{p^n} \text{ in } (\mathbb{Z}/p\mathbb{Z})[x]$
for any natural n.

Then, we have

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