I can prove the $n$ is prime case: If $n$ is prime, then since $k < n$ and $n$ is prime, the factor of $n$ in the numerator won't be cancelled out.

So the question boils down to

Let an integer $n>1$ be such that $n$ divides $\binom nk$ whenever $0<k<n$; show that $n$ is prime.

If $n$ is composite and even, then ${n \choose 2} = \frac{n(n+1)}{2}$ is not divisible by $n$ because it 'lost' a $2$ factor (and $n+1$ is odd), which takes care of this case.

However, I'm somewhat at a loss for what to do when $n$ is composite and odd. Any hints?

  • $\begingroup$ I believe the converse is not true. ${4\choose1} = 4 \equiv 0 \mod4$. $\endgroup$
    – Yiyuan Lee
    Feb 3 '14 at 13:51
  • $\begingroup$ Sorry if it was unclear, I meant for all $k$ such that $0 < k< n$, so then ${4 \choose 2} \equiv 2 \pmod 4$ $\endgroup$
    – MCT
    Feb 3 '14 at 13:53
  • 2
    $\begingroup$ Furthermore I don't believe this is a duplicate -- I need help with proving the converse of what is asked in the linked question; as far as I know these are two separate questions. $\endgroup$
    – MCT
    Feb 3 '14 at 14:00
  • $\begingroup$ ${9\choose 4}\equiv 0 \mod 9$ $\endgroup$
    – clark
    Feb 3 '14 at 14:09
  • $\begingroup$ @clark, Lee: You should repeat quantors. $\endgroup$ Feb 3 '14 at 14:09

It is well known (Kummer's theorem) that the multiplicity of a prime number $p$ in a binomial coefficient $\binom{a+b}a$, with $a,b\in\mathbf N$, equals the number of times a carry is produced when representing $a,b$ as numbers in base$~p$ and performing the addition $a+b$. Now if $n$ is composite and $p$ a prime divisor of$~n$, then first consider the case that $n$ is not a power of $p$. This means that in base$~p$ it has either two nonzero digits or a single nonzero digit other than $1$. Now by separating the nonzero digits in two non-empty groups respectively representing $a,b$, or doing similarly after writing the single nonzero digit as a carry-less sum of other digits, one can achieve $n=a+b$ without any carry in base$~p$; this means that $p\nmid\binom na$ and a fortiori $n$ does not divide $\binom na$. We are left with the case that $n=p^i$ for some $i\geq2$. But now with $a=p^i-p^{i-1}$ and $b=p^{i-1}$, their base$~p$ representations are $a=[p-1,0,\ldots,0]_p$ respectively $b=[1,0,\ldots,0]_p$ (with $i-1$ digits in each number), so perfoming $a+b$ produces a carry only once, and there is only one factor$~p$ in $\binom na$, which is therefore not divisible by $n=p^i$. This proves what you want.


Here's a simple proof by contrapositive. Suppose $n$ is not prime. Let $p$ be a prime divisor of $n$ and write $n=p^d q$, where $p\not\mid q$. Clearly $0<p<n$. Then $$\binom{n}{p}=\frac{p^d q\cdot(p^dq-1)\cdots (p^dq-(p-1))}{p!}\textrm.$$ There are exactly $d$ factors of $p$ in the numerator, all from the the term $p^dq$, because each term after that one differs from a multiple of $p$ by less than $p$ (and therefore can't be a multiple of $p$). One of those $d$ factors is cancelled out by the $p$ in the denominator, so $p^d \not\mid \binom{n}{p}$, which guarantees that $n\not\mid \binom{n}{p}$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.