Proof that p prime divides binominal coefficient with p k

Question

Let $p$ be prime and $k\in\mathbb N, \ 0 < k < p.$

Claim: $p | \begin{pmatrix}p \\ k \end{pmatrix}$

Proof:

We know that $\begin{pmatrix}p \\ k \end{pmatrix} = \frac{p!}{k!(p-k)!}=\frac{p(p-1)!}{k!(p-k)!}$

It's clear, that $\frac{p!}{k!(p-k)!}=\frac{p(p-1)!}{k!(p-k)!}$ is dividable by p. Thus $p | \frac{p!}{k!(p-k)!}=\frac{p(p-1)!}{k!(p-k)!}$ and thus $ p | \begin{pmatrix}p \\ k \end{pmatrix}$

q.e.d.

Does this work?

Answer 1

Your argument shows that $$\binom{p}{k} =p\left(\frac{(p-1)!}{k!(p-k)!}\right)$$ but it's not immediate that the factor ${\displaystyle{\frac{(p-1)!}{k!(n-k)!}}}$ is an integer.

To finish it, cross-multiply, and then use the primeness of $p$ . . . \begin{align*} \text{Thus,}\;\;&\binom{p}{k} =p\left(\frac{(p-1)!}{k!(n-k)!}\right)\\[4pt] \implies\;&p(p-1)!=(k!)\bigl((p-k)!\bigr)\binom{p}{k}\\[4pt] \end{align*}

Since $p$ is prime,

• $0 < k < p\implies p\not\mid k!$$\\[4pt]$

  [since $p$ does not divide any of the factors $1,..,k$]$\\[4pt]$

• $0 < k < p\implies 0 < p - k < p \implies p\not\mid (p-k)!$$\\[4pt]$

  [since $p$ does not divide any of the factors $1,..,p-k$]$\\[4pt]$

In the equation $$p(p-1)!=(k!)((p-k)!)\binom{p}{k}$$ it's clear that $p$ divides the LHS, hence $p$ divides the RHS.

Thus, $p$ divides the product of the $3$ integers $$k!,\;\;\;(p-k)!,\;\;\;\binom{p}{k}$$ hence, since $p$ is prime, $p$ must divide at least one of the $3$ factors.

Since $p\not\mid k!$, and $p\not\mid (p-k)!$, it follows that $p\,{\mid}\,{\large{\binom{p}{k}}}$, as was to be shown.

Answer 2

Note that $$ k!\binom{p}{k}=p(p-1)\cdots (p-k+1) $$ Suppose that towards a contradiction, $p$ does not divide $\binom{p}{k}$. Then because $p$ divides the LHS and $p\mid ab\implies p\mid a\quad \text{or}\quad p\mid b$, it follows that $p\mid k!$ so $p\mid j$ for some $1\leq j \leq k<p$, a contradiction.