2
$\begingroup$


I'm quite lost on how to prove things, with the $n \choose k$ and proving. So the question is:

Prove that $n \choose k$ is divisible by $n$ if $n$ is a prime number and $1 \le k\le n-1$


Like, how would I/you go about proving that $n \choose k$ is divisible and is a prime number??

Thanks

$\endgroup$
1
  • $\begingroup$ Well you can't prove that it's divisible and it's a prime number because these are contradictory statements. You want to prove that given the assumption than $n$ is prime and $1 \leq k \leq n - 1$, show that $\binom{n}{k}$ is divisible. One way to do this: show $\frac{\binom{n}{k}}{n}$ is an integer. $\endgroup$
    – dalastboss
    Mar 12, 2015 at 0:45

2 Answers 2

2
$\begingroup$

By definition, $\binom{n}{k}=\frac{n!}{k!(n-k)!}$. Also, since $k<n$ and $n$ is prime, then $k!$ and $(n-k)!$ both do not have a factor of $n$. Thus the quotient of $\frac{n!}{k!(n-k)!}$ is still divisible by $n$, as required.

$\endgroup$
3
  • $\begingroup$ Ok cool thanks @user45220 So, it's just like the normal equation (the Combinations equation), and then do the k! and (n-k)! separately $\endgroup$ Mar 12, 2015 at 0:48
  • $\begingroup$ Sorry, I do not understand your question. (But just for the sake of it, I will note that you shouldn't be discouraged that I replied so quickly because I once found this stuff hard as well, it just takes familiarity with basic number theory and stuff). $\endgroup$
    – user45220
    Mar 12, 2015 at 0:52
  • $\begingroup$ Sorry for not being so clear. I mean that, when proving these types, you would sort of separate parts of the equation (like what you did), and state why it may or may not work Sorry, just basically like a beginner at doing this Binomial stuff $\endgroup$ Mar 12, 2015 at 0:54
1
$\begingroup$

A simple proof that uses Gauß's lemma. The binomial coefficients satisfy this recursion formula, for $0<k<n$:

$$\binom nk=\frac nk\binom{n-1}{k-1}$$ If $n$ is prime, $k$ is coprime with $n$, hence it divides $\dbinom{n-1}{k-1}$. This proves $\dbinom nk=n\times\text{some factor}$.

For the second question, if I've well understood it, $\dbinom nk$ is prime if and only if $n$ is prime and $k=1$ or $n-1$.

Indeed, note first $\dbinom nk=1$ if $k=0,n$ and $\dbinom nk=n$ if $k=1,n-1$. Secondly, if $2\le k\le n-2$, the relation above is a non-trivial factorisation of $\dbinom nk$, whence the assertion.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .