# Proving prime $p$ divides $\binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$

Prove if $p$ is a prime then $p \mid \binom pk$ for $k\in\{1,\ldots,p-1\}$

I don't really know where to begin with this one.

I can see that I have to use the fact that $p$ is prime somewhere - the same is not true for composite numbers, for example $4\nmid 6=\binom42$.

I have checked that this is true for the first few primes:

• $3$ divides $\binom 31=\binom32=3$
• $5$ divides both $\binom 51=\binom 54=5$ and $\binom 52=\binom 53=10$
• $7$ divides $\binom71=\binom76=7$, $\binom72=\binom75=21$ and $\binom73=\binom74=35$.
• More generally $\,\displaystyle\dfrac{\gcd(n,m)}n{n\choose m}$ is an integer. OP is special case $\,n\,$ prime. – Bill Dubuque Nov 28 '16 at 3:23
• A nice solution is also to use the fact that $p\mid p\binom{p-1}{k-1} = k\binom pk$ given in this answer. – Martin Sleziak Jan 7 '17 at 19:46

$\binom{p}{k} = \frac{p!}{k!(p-k)!} = \frac{p(p-1)...(p-k+1)}{k!}$

since $\binom{p}{k}$ is an integer, and none of the members of $k!$ can divide p ( since it's a prime), then $p|\binom{p}{k}$

There is a really nice way to phrase this, that should introduce you to some notation you should really know.

Let us define the function $v_p:\mathbb{Z}\to\mathbb{N}\cup\{\infty\}$ by defining $v_p(x)$ to be the highest $i$ such that $p^i$ divides $x$ (where we take $v_p(0)=\infty$). Let us then extend $v_p$ to a map $v_p:\mathbb{Q}\to\mathbb{Z}$ by setting $v_p\left(\frac{a}{b}\right)=v_p(a)-v_p(b)$. One can quickly check that $v_p$ enjoys the following nice property:

$$v_p(xy)=v_p(x)+v_p(y)\quad\mathbf{(1)}$$

Moreover, we see by mere definition, that $p\mid x$ for $x\in\mathbb{Z}$ if and only if $v_p(x)>0$. Now, note that by $\mathbf{(1)}$ we have that

\displaystyle \begin{aligned}v_p\left({p\choose k}\right) &= v_p\left(\frac{p!}{k!(p-k)!}\right)\\ &= v_p(p!)-v_p(k!)-v_p((p-k)!)\end{aligned}\quad\mathbf{(2)}

But, since $\ell!=1\cdots \ell$ we can use $\mathbf{(1)}$ again to deduce that for each $\ell\in\mathbb{N}$ one has that

$$v_p(\ell!)=\sum_{j=1}^{\ell}v_p(j)$$

Now, if $j<p$ then evidently $p\nmid j$ so that $v_p(j)=0$. Thus,

$$v_p(k!)=\sum_{j=1}^{k}v_p(j)=\sum_{j=1}^{k}0=0$$

and

$$v_p((p-k)!)=\sum_{j=1}^{p-k}v_p(j)=\sum_{j=1}^{p-k}0=0$$

But

$$v_p(p!)=\sum_{j=1}^{p}v_p(j)=\sum_{j=1}^{p-1}v_p(j)+v_p(p)=\sum_{j=1}^{p-1}0+1=1$$

Thus, using $\mathbf{(2)}$ we may conclude that

$$v_p\left({p\choose k}\right)=1-0-0=1$$

and thus $\displaystyle p\mid {p\choose k}$, and moreover $p$ is the highest power of $p$ dividing ${p\choose k}$.

• Excellent and beautiful way to explain the solution. +1! :) – Ory Band Jan 27 '14 at 15:19
• I do really like this way of thinking, but I also believe that in this case a simple divisibility argument is more straightforward and generalizable. For example, if I wanted to prove a very related fact to that asked in the question, say that $p^m \mid \binom{p^m}{k}$ so long as $p \nmid k$, then I don't see much help from the $v_p$ map setup, whereas a one line divisibility argument still suffices. – Badam Baplan Apr 28 '16 at 19:20
• The proof is correct, but we can show this result in two lines, as @kaharas's answer shows. So what is the notation we should know that makes this proof useful? – Math1000 Dec 28 '19 at 9:27

let $a = (p-1)!$ and $b = k!(p-k)!$ then $\binom pk = p*(a/b)$ so $b*\binom pk = p*a$. So therefore $p\mid b*\binom pk$ and $p$ does not divide $b$ since it is a product of natural numbers each one being less than $p$. so therefore since $p$ is prime $p\mid \binom pk$.

With a tiny bit of group theory, you can do without using factorisation into primes.

Let $X=\{0,1,\ldots,p-1\}$, and let $f:X\to X$ be the shift operation $x\mapsto (x+1)\bmod p$. Clearly $f^p$ is the identity on$~X$. This function also gives an operation $\overline f:\mathcal P(X)\to\mathcal P(X)$ from the collection $\mathcal P(X)$ of $2^p$ subsets of $X$ to itself: $\overline f:S\mapsto\{\,f(x)\mid x\in S\,\}$.

The bit of group theory is that repeating $\overline f$ either gives a orbit of size $1$ or of size$~p$: for given $S$ either $\overline f(S)=S$, or else the $p$ subsets $S,\overline f(S),\overline f{}^2(S),\ldots,\overline f{}^{p-1}(S)$ are all different. Less formally: rotating a necklace of $p$ coloured beads by unit steps either gives just one colouring (for a monochrome necklace) or else $p$ different colourings. One also sees that $\overline f(S)=S$ only occurs when $S=\emptyset$ or $S=X$.

The subset $\overline f(S)$ of $X$ always has the same size as $S$. So iterating $\overline f$ partitions the $\binom pk$ subsets of size$~k$ into orbits of size$~p$, provided $k\notin\{0,p\}$ to exclude the fixed points $\emptyset$ and$~X$. This proves $p\mid\binom pk$.

You can also show the orbit property without group theory. Suppose some pair among the subsets $S,\overline f(S),\overline f{}^2(S),\ldots,\overline f{}^{p-1}(S)$ coincide: $\overline f{}^k(S)=\overline f{}^l(S)$ for $0\leq k<l<p$. Then because $\overline f$ is invertible one must have $\overline f{}^{l-k}(S)=S$; putting $d=l-k$ and iterating one gets that also $\overline f\,{}^{nd}(S)=S$ for $n=1,2,3,\ldots$. Since $d$ does not divide$~p$ and the exponents $nd$ can be reduced modulo$~p$ (as $\overline f\,{}^p$ is the identity), one of those powers reduces to $1$, so one concludes that $\overline f(S)=S$.

• Why does iterating $\overline f$ partition the $\binom pk$ subsets of size $k$ into orbits of size $p$? Why is it that the subsets $S,\bar f(S), \ldots, \bar f^{p-1}(S)$ are all different? – Math1000 Dec 28 '19 at 9:35
• We have an action of a group of $p$ elements, and group theory says that the size of orbits divide the order of the acting group; that means here that orbits either have a single element or $p$ distinct elements (since $p$ is prime). In other words those subsets are either all the same (which happens when $S=\emptyset$ or $S=X$) or else they are all distinct. – Marc van Leeuwen Dec 28 '19 at 22:49
• Thanks! I suppose that is somewhat similar to Lagrange's theorem, in that the order of a subset of a group must divide the order of a group? – Math1000 Dec 28 '19 at 22:51
• Subgroup of a group, and yes it is somewhat similar. Probably even a special case, though Lagrange's theorem is usually taught first, and separately of group actions. – Marc van Leeuwen Dec 28 '19 at 22:54

By definition, $$\binom{p}{k}$$ can be expanded as follows:
$$\binom{p}{k}$$ = $$\frac{p!}{k!(p - k)!}$$

Since $$\binom{p}{k}$$ is a positive integer number by definition, let's denote it as $$n$$, $$n \in \mathbb N$$.
$$n$$ = $$\frac{p!}{k!(p - k)!}$$

Now, move the denominator to the left side:
$$n$$ $$\cdot$$ $$k!(p - k)!$$ = $$p!$$

$$p!$$ is obviously divisible by $$p$$.
Hence, $$n$$ $$\cdot$$ $$k!(p - k)!$$ is also divisible by $$p$$. So, at least one factor must be divisible by $$p$$:

1. $$k!$$ is not divisible by $$p$$ because $$k < p$$ and $$p$$ is prime.
2. $$(p - k)!$$ is not divisible by $$p$$ because $$(p - k) < p$$ and $$p$$ is prime.

Thereof, $$p \mid n \Rightarrow p \mid \binom{p}{k}$$

Hint $\rm\ mod\ p\!:\ (x\!+\!1)^p\!-x^p\!-1 =\, 0,\:$ having degree $\rm < p,\,$ and roots $\rm\,1,2,\ldots, p\:$ by little Fermat.

Recall $${\displaystyle {p\choose k}=\frac{p!}{k!(p-k)!}=\frac{p\cdot p-1\cdot p-2\cdots 2\cdot1}{k\cdot k-1\cdots 2\cdot1\cdot p-k\cdot p-k-1\cdots2\cdot1}}$$ and $$a\mid b\Rightarrow b=a\cdot m$$, where $$m\in\mathbb{Z}$$. Since $$k\leq p-1$$, it is obvious to assume $$k, i.e., $$k!$$ is contained somewhere in $$p!$$, so these terms will cancel out (honestly this step isn't even necessary, but it is nice to see expressions in lowest terms). The final term remaining in $$p!$$ will be $$k+1$$ in terms of $$p$$; denote this by $$(k+1)^*$$. This leaves us with $$\frac{p\cdot p-1\cdots (k+1)^*}{p-k\cdot p-k-1\cdots2\cdot1}$$. If we factor out $$p$$, then we obtain $${\displaystyle{p\choose k}=p\cdot\frac{p-1\cdots (k+1)^*}{p-k\cdot p-k-1\cdots2\cdot1}}$$. Note that this holds since $${\displaystyle{p\choose k}}$$ is an integer and $$k!\nmid p$$ (as mentioned above). Clearly $$p$$ divides $${\displaystyle{p\choose k}}$$.