16
$\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
    $\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
  • 1
    $\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
20
$\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$
  • 3
    $\begingroup$ But how to be sure that $\frac{(p-1)...(p-k+1)}{k!}$ is an integer ? $\endgroup$ – MSE Dec 20 '15 at 21:11
  • 3
    $\begingroup$ @MSE: Since $p (p-1) \dots (p-k+1) = \binom p k k!$ and $k! \nmid p$ (because $p$ is prime), then $k! \mid (p-1) \dots (p-k+1)$, so $\frac {(p-1) \dots (p-k+1)} {k!}$ is an integer. $\endgroup$ – Alex M. Jan 24 '16 at 16:30
  • $\begingroup$ @AlexM.: It's not sufficient to note that $k! \nmid p$, because $n \mid ab$ does not imply that $n \mid a$ or $n \mid b$ (e.g. $6 \mid 3 \cdot 4$, but $6 \nmid 3$ and $6 \nmid 4$). You need to use the fact that $k! \perp p$, because $n \mid ab$ and $n \perp a$ does imply that $n \mid b$. $\endgroup$ – Sic Vis Oct 3 '17 at 21:29
  • 1
    $\begingroup$ @SicVis: Remember that $p$ above is prime, which is what I have always had in mind while writing all of the above. Please let's not waste time anymore with such elementary matters. $\endgroup$ – Alex M. Oct 4 '17 at 17:34
  • 1
    $\begingroup$ It follows directly from the recursive definition of ${n\choose k}$ that it is a natural number. $\endgroup$ – GuillaumeDufay Dec 10 '17 at 2:25
16
$\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$
  • $\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
5
$\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$
4
$\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$
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$

Your Answer

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