20
$\begingroup$

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$.
$\endgroup$
2
  • 2
    $\begingroup$ More generally $\,\displaystyle\dfrac{\gcd(n,m)}n{n\choose m} $ is an integer. OP is special case $\,n\,$ prime. $\endgroup$ – Bill Dubuque Nov 28 '16 at 3:23
  • 2
    $\begingroup$ 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. $\endgroup$ – Martin Sleziak Jan 7 '17 at 19:46
29
$\begingroup$

$\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}$

$\endgroup$
0
18
$\begingroup$

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}$.

$\endgroup$
3
  • $\begingroup$ Excellent and beautiful way to explain the solution. +1! :) $\endgroup$ – Ory Band Jan 27 '14 at 15:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Badam Baplan Apr 28 '16 at 19:20
  • $\begingroup$ 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? $\endgroup$ – Math1000 Dec 28 '19 at 9:27
8
$\begingroup$

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$.

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – Math1000 Dec 28 '19 at 9:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Dec 28 '19 at 22:49
  • $\begingroup$ 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? $\endgroup$ – Math1000 Dec 28 '19 at 22:51
  • $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Dec 28 '19 at 22:54
3
$\begingroup$

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}$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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<p$, 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}}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy