Proof: if $p$ is prime, and $0<k<p$ then $p$ divides $\binom pk$

Question

Question : If $p$ is prime, and $0< k< p$ show that $ p \mid {p \choose k}$

${p \choose k}$ can be rewritten as:

$${p(p-1)(p-2)\dots(p-(k-1))(p-k)! \over (p-k)!\cdot k(k-1)(k-2)\dots3\cdot2\cdot1}$$

Now the $(p-k)!$ cancels out. Since in the numerator we have k consecutive integers, k divides one of them (not p as p is prime and $k <p$). Then k-1 divides another one or two terms in the k consecutive terms (again not p). This reasoning continues until 3 and 2.

This means that ${p \choose k}$ can be rewritten as pq implying $p | {p \choose k}$

What if any of this proof is wrong. I am worried about any 'overlaps', i.e. say k-6 divides terms that k-3 divides invalidating the argument.

P.S. I hope the above is legible as I am new to this site. Thank you!

Answer 1

We have $${p\choose k}=\frac{p}{k}{{p-1}\choose {k-1}}$$ and since $(p,k)=1$, then $p|{p\choose k}$.

Answer 2

Writing explicitely $\frac{p!}{k!(p-k)!}$ there is a unique multiple of $p$ at the numerator. But this is an integer, hence it is a multiple of $p$.

---

Your argument cannot be false, meaning there is no overlap. I will try to be more explicit:

$$\binom{p}{k}=\frac{p\cdot (p-1) \cdots (p-k+1)}{k \cdot (k-1) \cdots 1}$$

We all have already agreed that, if this is an integer, then this is a multiple of $p$. The question can be then reformulated: why $\binom{p}{k}$ has to be an integer?

Motivation 1 (combinatorial interpretation, at first it may look like a cheating answer, but this is not): $\binom{p}{k}$ is the number of ways to choose $k$ objects into $p$ identical objects.

Motivation 2: it would be enough to prove that if $q^\alpha$ divides exactly the denominator (for some prime $q \le k < p$ then $q^\alpha$ divides also the numerator. How to show it? Algebraically, the number factors $q$ which divides $n!$ is exactly $$\sum_{i \ge 1}\left\lfloor \frac{n}{q^i}\right\rfloor.$$ This is commonly known as Polignac's formula. Hence, we have to show equivalently that for each prime $q<p$ we have $$\sum_{i \ge 1}\left\lfloor\frac{p}{q^i}\right\rfloor \ge \sum_{i \ge 1}\left\lfloor \frac{p-k}{q^i}\right\rfloor+\sum_{i \ge 1}\left\lfloor \frac{k}{q^i}\right\rfloor.$$ But this is immediate, since for each positive $x,y$ we have $\lfloor x+y\rfloor \ge \lfloor x\rfloor +\lfloor y\rfloor$. The claim follows summing over $i$.

---

More generally, this argument can be modified for all strongly divisible sequence, i.e. sequences $(a_n)_{n \in \mathbf{N}}$ such that $\text{gcd}(a_n,a_m)=a_{\text{gcd}(n,m)}$. [For instance, it works for Fibonacci numbers].

Answer 3

I will try to give a fun proof. Take $k$ such that $0 < k < p$. The group $\mathbf{F}_p = \mathbf{Z}/p\mathbf{Z}$ acts on the set $X$ of subsets of $\mathbf{F}_p$ of cardinal $k$, namely by $Y\in X\mapsto Y+\alpha :=\{ y+\alpha \; | \; y \textrm{ in } Y \} \in X$ for every $\alpha\in \mathbf{F}_p$. (As translation are bijective, they preserve the cardinal, so that sets of cardinal $k$ are indeed sent to sets of cardinal $k$.) This action induces a partition of $X$ into orbits, and a well-known elementary group theory results ensures that each orbit has a cardinal dividing the cardinal of the group $\mathbf{F}_p$, that is, dividing $p$. As $p$ is prime, each orbit must have a cardinal equal to $1$ or $p$. Now, imagine there is an orbit of cardinal $1$. This means that there is a subset $J$ (of cardinal $k$) of $\mathbf{F}_p$ that is stable by all translation by elements $\alpha \in\mathbf{F}_p$ and as $k > 0$, this set $J$ is non-empty, so let $x$ be in it. Then $1 = x + \underbrace{(1-x)}_{:=\alpha\in\mathbf{F}_p}$ is in it. As $1$ generates the additive group $\mathbf{F}_p$, we see that $J$ contains in fact whole $\mathbf{F}_p$, violating thereby the hypothesis $k < p$. Therefore, there is no orbit of cardinal $1$, and by the previous observation, all orbits must have cardinal $p$. As $X$ is disjoint union of orbits, the cardinal of $X$ is simply equal to $np$, where $n$ is the number of disctinct orbits. But what is the cardinal of $X$ ? Remember, $X$ is the set of subsets of $\mathbf{F}_p$ (who is a set a cardinal $p$) that have cardinal $k$. So the cardinal of $X$ is ${p \choose k}$, which is divisible by $p$. $\square$

Answer 4

Kummer's Theorem, a proof of which is given in this answer, says that the number of factors of $p$ in $\binom{n}{k}$ is the number of base-$p$ carries when adding $k$ and $n-k$. When adding $k$ and $p-k$ in base-$p$, we get one carry if $0\lt k\lt p$. Therefore, there is exactly one factor of $p$ in $\binom{p}{k}$ for $0\lt k\lt p$.

If we apply formula $(1)$, with $\sigma_p(k)=k$ and $\sigma_p(p-k)=p-k$ and $\sigma_p(p)=1$, we get the number of carries to be $$ \frac{\sigma_p(k)+\sigma_p(p-k)-\sigma_p(p)}{p-1}=\frac{k+(p-k)-1}{p-1}=1 $$

Answer 5

You can also write $k {p\choose k} = (p-k+1) {p \choose k-1}$ and do an induction on $k$.

Answer 6

Lucas theorem says $\displaystyle \binom n k \equiv \binom {\left \lfloor {n / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor} \binom {n \bmod p} {k \bmod p} \pmod p$, let $p=n$ then we have $$\displaystyle \binom p k \equiv \binom {\left \lfloor {p / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor} \binom {p \bmod p} {k \bmod p} \pmod p$$ and $p\equiv0\pmod p$ , if $0 < k < p$ we have $k \bmod p \ne 0$ but $$\displaystyle \binom {p \bmod p} {k \bmod p} = \binom 0 {k \bmod p} = 0$$ from which the result is derived