Show that the number of binomial coefficients not divisible by 3 is not divisible by 5 where the binomial coefficients are: .

- December 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: .

- December 29th 2009, 06:05 PMabender
Hint: Write in the base 3 and let { } be the digits which appear. The number of binomial coefficients not divisible by 3 is then given by .

Note that this works for any prime , not just 3. - December 31st 2009, 07:13 AMjames_bond
- December 31st 2009, 11:10 PMabender
- January 1st 2010, 01:03 AMjames_bond
- January 1st 2010, 01:59 AMabender
Let

Let denote the number of binomial coefficients .

Now, assume that whereby

Now, we want to show that

It is obvious that , for all .

As a result, .

Then through induction, we show that for any natural n.

Then, we have

Then, when developing factors on the right-hand side, we get a sum of the factors , 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 of these factors, which means that the number of binomial coefficients not divisible by p is

Do your best to finish this.