1
$\begingroup$

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.

  • 0
    A binomial entourage... :)2012-03-08

1 Answers 1

4

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

  • 0
    @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!2012-03-08