If $n,k\in\Bbb{N}$ and $\binom{n}{k}$ is a prime number, then $k = 1$ or $k = n−1$

Question

I need help prooving that if $n,k\in\Bbb{N}$ and $\binom{n}{k}$ is a prime number, then $k = 1$ or $k = n−1$.

Answer 1

We will use two facts about binomial coefficients. The first fact is the fairly obvious observation that

$${n\choose1}={n\choose n-1}=n\quad\text{and}\quad{n\choose k}\gt n\quad\text{for }1\lt k\lt n-1$$

The second fact is a crucial divisibility property:

$$n\mid(n,k){n\choose k}\quad\text{for }0\lt k\lt n$$

The inequality in the first fact follows easily from the equality ${n\choose k}={n-k\over k}{n\choose k-1}$. As for the second fact, imagine $n$ objects arranged in a circle, $k$ of which are black and the others white. Any rotation of such an arrangement by $h$ places, with $0\le h\lt n/(n,k)$, gives a different arrangement. This implies $n/(n,k)$ divides $n\choose k$, which means $n$ divides $(n,k){n\choose k}$.

Now assume that ${n\choose k}=p$ is prime. Then the second fact implies $(n,k)p=nm$ for some $m$. But $0\lt k\lt n$ implies $(n,k)\lt n$, so $nm=(n,k)p\lt np$, which implies $m\lt p$, which in turn implies $p\not\mid m$, which in turn implies $p\mid n$, which implies $n\ge p$. Invoking now the first fact, we have $p={n\choose k}\ge n\ge p$, so that we must have $n=p={n\choose k}$, and therefore $k=1$ or $n-1$.

Answer 2

Try to think about when $$\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$$ is a prime number.

What happen when $k\notin\{1,n-1\}$ ?

Answer 3

By cyclically shifting the choice of $k$ elements from $n$ elements and adding $1$ more choice of $k$ elements from $n$ elements which is possible iff $k \neq 1,n-1$, we get, $${n \choose k} > n, for \ k \neq 1,n-1$$

1. ${n \choose k}$ cannot have prime factors $>n$.
2. ${n \choose k} = p$ prime according to hypothesis.
3. ${n \choose k} > n$ for $k \neq 1,n-1$ according to above argument.

Points 1,2,3 are inconsistent for $k \neq 1,n-1$. Hence the hypothesis in point 2) that ${n \choose k}$ is prime is not possible unless $k = 1 \ or \ n-1$.