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.
 A: 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).
