How to find exponent of a number in a combination?

Question

How do I find the exponent of $7$ in $^{100}C_{50}$ that is, $\dfrac{100!}{(100-50)!\cdot 50!} =\dfrac{100!}{50!\cdot 50!}$,

this question was out of the blue, and I haven't been able to find any worked out examples on it. I'm new to permutations and combinations and frankly didn't understand what the question is asking. :-(

It'll be great if someone could explain the question and also suggest the way to go about it..

cheers! :-)

Answer 1

Take a prime $p$ and an integer $n$. By Legendre's theorem the largest power of $p$ dividing $n!$ is given by the sum: $$ \sum_{k \ge 1} \left\lfloor \frac{n}{p^k} \right\rfloor $$ (the sum is really finite). Use this thrice.

Answer 2

Note that there are $14$ multiples of $7$ less than or equal to $100$, and $2$ of these are multiples of $49 = 7^2$ (and $0$ multiples of $343 = 7^3$, etc.). So all in all, $7^{16}$ (counting each of the multiples of $7$ once, and then counting the multiples of $49$ an additional time, so $14 + 2 = 16$) is the largest exponent of $7$ that divides $100!$.

Repeating this for $50!$, we get that $7^8$ is the largest exponent of $7$ dividing $50!$. So $7^{16} / 7^8 7^8 = 1$.

$7$ does not divide $\left( \begin{array}{c} 100 \\ 50 \end{array} \right)$.

Answer 3

In this answer, it is shown that for a prime $p$, the number of factors of $p$ that divide $\binom{n}{k}$ is $$ \frac{\sigma_p(k)+\sigma_p(n-k)-\sigma_p(n)}{p-1}\tag{1} $$ where $\sigma_p(n)$ is the sum of the digits of $n$ in base-$p$.

$100_\text{ten}=202_\text{seven}$ and $50_\text{ten}=101_\text{seven}$. Therefore, the number of factors of $7$ in $\binom{100}{50}$ is $$ \frac{2+2-4}{6}=0\tag{2} $$ Thus, $\binom{100}{50}$ is not divisible by $7$.