# Finding number of entries not divisible by number n in 100th row of pascal's triangle

Here is a question related to Pascal's triangle. I need to find the number of entries not divisible by $n$ in the 100th row of Pascal's triangle.

-
The $n$th row of Pascal's triangle constains the number $\binom{n}{0}$, $\binom{n}{1}$, $\binom{n}{2},\ldots,\binom{n}{n}$. One can determine when $\binom{n}{k}$ is divisible by 3 by considering the number of carries when adding $k$ and $n-k$ in base $3$: if there is at least one carry, then it is divisible by $3$; if there are no carries, then it is not divisible by $3$. – Arturo Magidin Mar 8 '12 at 18:21
We need to do this??? – The Chaz 2.0 Mar 8 '12 at 18:21
@TheChaz: Not "we", "they": Mr Jay and his entourage. – Arturo Magidin Mar 8 '12 at 18:22
A binomial entourage... :) – The Chaz 2.0 Mar 8 '12 at 18:30

You can use Kummer's theorem.

Kummer's theorem gives you a method to find the highest power of a prime $p$ which divided the binomial coefficient $\binom{a}{b}$. It says that the require exponent is the number of carries when you add $b$ and $a-b$ in base $p$.

Now if you want to check the divisibility of $\binom{a}{b}$ by a given number $n$, you first factorize $n$ into prime factors: $n = p_1^{e_1} \dots p_k^{e_k}$ and then for each $p_i$, try to find the highest power of $p_i$ which divides $\binom{a}{b}$ using Kummer's theorem. Say you find it to be $s_i$.

Now you just check for each $i$ whether $s_i \ge e_i$.

To give you an example, suppose you want to find out if $\binom{100}{77}$ is divisible by $20$.

$20 = 2^2 \times 5$.

Now write $77 = 64 + 8 + 4 + 1 = 1001101_2$

$100 - 77 = 23 = 16 + 4 + 2 + 1 = 0010111_2$.

Add the two and you see that there are $5$ carries. So $2^5$ divides $\binom{100}{77}$.

Now do the same in base $5$. $77 = 25*3 + 2*1 = 302_5$.

$23 = 5*4 + 3*1 = 43_5$

Add the two and you see there are $2$ carries. So $5^2$ divides $\binom{100}{77}$.

Thus $\binom{100}{77}$ is divisible by $20$.

Now do each in the 100th row, and you have your answer.

Another method is to use Legendre's theorem:

The highest power of $p$ which divides $n!$ is $\left[\frac{n}{p}\right] + \left[\frac{n}{p^2}\right] + \left[\frac{n}{p^3}\right] + \dots$

To use this, use the fact that $\binom{a}{b} = \frac{a!}{(a-b)!b!}$ and use the above to each factorial that is appearing, subtracting the answer you get for the factorials in the denominator.

This is probably a bit more tedious than using Kummer's method though.

(Note: there might be cleverer ways to just find the count you are interested in).

-
ok..well i wanted to know if i can calculate this manually.Can u explain how to work out this using the theorem you just stated. – Jay Mar 8 '12 at 18:30
@Jay: I suggest you try it out yourself first! – Aryabhata Mar 8 '12 at 18:32
i know i may sound silly but i am not good with maths , so can u please explain Kummer's Theorem.i tried but could understand it..the last part "the number of carries when adding m and n−m in base p" – Jay Mar 8 '12 at 18:47
@Jay: Do you know how to change the base of a number? Do you know how to add two numbers written in a given base? Do you know how a carry happens during addition? – Aryabhata Mar 8 '12 at 18:54
@Jay: I have elaborated a bit. I wanted you to try it for your own benefit (hands on experience and all that), but perhaps an example will help too. Good luck! – Aryabhata Mar 8 '12 at 21:05