0
$\begingroup$

let C be the choose function, defined as:

$C(n,k)=\frac{n!}{k!(n-k)!)}$

Why can't C(n,k) have a prime factor larger than n?

I don't know much about the relationship between the binomial coefficient and prime factors and was wondering if I could just be pointed in the right direction.

Take C(47,11) for example. It is equal to 17417133617. To me this seems to be an arbitrary large number. How can I tell that this number, from the information that it is C(47,11), has no prime factor larger than 47?

The reason I have this question is that I observed this trait after solving a problem (I verified it with several testcases by writing a short Python program that finds all the prime factors of a number), but have been unable to prove it or explain why.

$\endgroup$
5
$\begingroup$

Since $\binom{n}{k}=\frac{n!}{k!(n-k)!}$, we know that any prime $p$ that divides $\binom nk$ also divides $n!$ (since dividing by integers can't add factors). Because $n!$ contains only factors $\leq n$, it cannot have a prime factor greater than $n$.

$\endgroup$
  • $\begingroup$ Thanks for the succinct explanation, makes perfect sense now. $\endgroup$ – Noob Coder Dec 29 '13 at 2:40
  • 2
    $\begingroup$ Remark that this argument implicitly uses uniqueness of prime factorizations or, equivalently, if a prime divides a product then it divides some factor of the product. $\endgroup$ – Bill Dubuque Dec 29 '13 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.